Korthedsindeks

Korthedsindekset er en numerisk parameter for en familie af grafer, der angiver, hvor langt fra at være Hamiltonsk , familiens grafer kan være. Intuitivt, hvis er et mål for kortheden af ​​en graf af familien , så har enhver graf med hjørner en cyklus med længde tæt på , men nogle grafer har ikke længere cyklusser. Mere præcist, for enhver rækkefølge af grafer i sekvensen og en funktion defineret som længden af ​​den længste cyklus i grafen , er korthedsindekset defineret som [1]

Dette tal er altid i intervallet fra 0 til 1. Eksponenten er 1, hvis familiens grafer altid indeholder Hamiltonianere eller en cyklus tæt på Hamiltonian, og 0, hvis den største længde af cyklusser i familiens grafer kan være mindre end enhver konstant potens af antallet af toppunkter.

Korthedsindekset for polyedriske grafer er . En konstruktion baseret på Klee polyeder viser, at nogle polyedriske grafer har den største længdecyklus [2] , og det er også blevet bevist, at enhver polyedrisk graf indeholder en længdecyklus [3] . Polyedriske grafer er grafer, der er både plane og 3-vertex-forbundne . Det faktum, at toppunkt 3-forbundet er vigtigt her, skyldes, at der er mange toppunkt-2-forbundne plane grafer (såsom komplette todelte grafer ) med korthedseksponent 0. Der er mange yderligere resultater vedrørende korthedseksponenten af ​​afgrænsede underklasser af plane og polyedriske grafer [1] .

Vertex-3-forbundne kubiske grafer (uden planaritetskravet) har også en korthedseksponent, der (som det er vist) ligger strengt mellem 0 og 1 [4] [5] .

Noter

  1. ↑ 1 2 Grünbaum, Walther, 1973 , s. 364-385.
  2. ↑ Moon, Moser, 1963 , s. 629-631.
  3. ↑ Chen, Yu, 2002 , s. 80-99.
  4. ↑ Bondy, Simonovits, 1980 , s. 987-992.
  5. ↑ Jackson, 1986 , s. 17-26.

Litteratur