Lyhytisyysindeksi

Lyhyusindeksi on kaavioperheen numeerinen parametri, joka osoittaa kuinka kaukana Hamiltonin kaaviot perheen graafit voivat olla. Intuitiivisesti, jos on perheen graafin lyhyyden mitta , niin minkä tahansa graafin, jolla on pisteet, syklin pituus on lähellä , mutta joillain kaavioilla ei ole pidempiä syklejä. Tarkemmin sanottuna, minkä tahansa kaavioiden järjestyksen sekvenssissä ja funktiolle , joka on määritelty kaavion pisimmän syklin pituudeksi , lyhyysindeksi määritellään [1]

Tämä luku on aina välillä 0 - 1. Eksponentti on 1, jos perheen kaavioissa on aina Hamiltoneja tai Hamiltonin läheinen sykli, ja 0, jos perheen kaavioiden suurin syklien pituus voi olla pienempi kuin mikä tahansa pisteiden lukumäärän vakio potenssi.

Monitahoisten graafien lyhyusindeksi on . Klee-polyhedraan perustuva konstruktio osoittaa, että joillakin monitahograafisilla graafilla on suurin pituussykli [2] , ja on myös todistettu, että mikä tahansa monitahograafi sisältää pituussyklin [3] . Monitahoiset graafit ovat graafeja, jotka ovat sekä tasomaisia ​​että 3-kärkiliitoksia . Se, että kärkipisteen 3-yhteydet ovat tärkeitä tässä, johtuu siitä, että on olemassa monia kärki-2-liitettyjä tasokaavioita (kuten täydellisiä kaksiosaisia ​​graafisia kaavioita ), joiden lyhyyseksponentti on 0. On olemassa monia lisätuloksia taso- ja monitahoisten rajattujen alaluokkien lyhyydestä. kaavioita [1] .

Vertex-3-liitetyillä kuutiograafilla (ilman tasomaisuusvaatimusta) on myös lyhyuseksponentti, joka (kuten on esitetty) on tiukasti välillä 0 ja 1 [4] [5] .

Muistiinpanot

  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.

Kirjallisuus