Moore gróf

Megoldatlan problémák a matematikában : létezik-e Moore-gráf 5-ös kerülettel és 57-es fokozattal?

A Moore-gráf fokszámú és átmérőjű szabályos gráf , amelynek csúcsainak száma megegyezik a felső korláttal $d$ $k$

1+d\sum _{i=0}^{k-1}(d-1)^{i}.

A Moore-gráf egyenértékű definíciója egy kerületi átmérőjű gráf . A Moore-gráf egy másik ekvivalens definíciója egy olyan gráf, amelynek kerülete pontosan hosszú ciklusokkal rendelkezik , ahol a csúcsok és élek száma . A gráfok valójában szélsőségesek a ciklusok számához képest, amelyek hossza megegyezik a gráf kerületével [1] . $k$ $2k+1$ $G$ $g=2k+1$ ${\frac {n}{g}}(m-n+1)$ $g$ $n$ $m$ $G$

A grafikonokat Alan Hoffman és Robert Singleton [2] Edward Moore után nevezte el , aki felvetette az ilyen gráfok leírásának és osztályozásának kérdését.

Mivel egy adott fokszám és átmérő kombinációhoz a lehető legtöbb csúcs van, a Moore-gráfok a lehető legkisebb csúcsokkal rendelkeznek egy adott fokszámú és kerületű szabályos gráfokhoz. Így bármely Moore-gráf cella [3] . A Moore-gráf csúcsainak számának képlete általánosítható, hogy páros kerületű Moore-gráfokat definiálhassunk, és ezek a gráfok ismét cellák.

A csúcsok számának korlátai fok és átmérő szerint

Legyen tetszőleges gráf, amelynek maximális foka és átmérője van, akkor veszünk egy szélesség-első kereséssel kialakított fát , amely a csúcsban gyökerezik . Ennek a fának van 1 0. szintű csúcsa (maga a csúcs ), és maximum 1. szintű csúcsai (a csúcs szomszédai ). A következő szintnek maximum csúcsa van – a csúcs minden szomszédja egy élt használ a csúcshoz való csatlakozáshoz , tehát maximum 2. szintű szomszédai lehetnek. Általában az ehhez hasonló argumentumok azt mutatják, hogy bármely szinten legfeljebb csúcs lehet. Így a csúcsok teljes száma legfeljebb lehet $G$ $d$ $k$ $v$ $v$ $d$ $v$ $d(d-1)$ $v$ $v$ $d-1$ ${\displaystyle 1\leq {i}\leq {k))$ ${\displaystyle d(d-1)^{i))$

1+d\sum _{i=0}^{k-1}(d-1)^{i}.

Hoffman és Singleton [2] eredetileg úgy határozta meg a Moore-gráfot, mint egy olyan gráfot, amelynél ez a csúcsok számának korlátja elérhető. Így bármely Moore-gráfnak a lehető legnagyobb számú csúcsa van az összes gráf közül, amelyek foka nem haladja meg a -t, és az átmérője . $d$ $k$

Később Singleton [4] kimutatta, hogy a Moore-gráfok ekvivalens módon definiálhatók átmérővel és kerülettel rendelkező gráfként . Ez a két követelmény kombinálva van, amiből a gráf d -szabályossága bizonyos -ra levezethető . $k$ $2k-1$ $d$

Moore-gráfok cellákként

A gráf csúcsainak maximális fokszámának és átmérőjének felső korlátja helyett használhatunk egy alsó korlátot a csúcsok számának minimális fokára és kerületére vonatkozóan [3] . Tegyük fel, hogy a gráfnak van egy minimális foka és kerülete . Kiválasztunk egy tetszőleges kezdőcsúcsot , és a korábbiakhoz hasonlóan elképzelünk egy szélesség-első keresési fát, amelynek gyökere a -ben van . Ennek a fának rendelkeznie kell egy csúcsponttal a 0. szinten (maga a csúcs ) és legalább az 1. szinten lévő csúcsokkal. A 2. szinten (for ) legalább csúcsnak kell lennie, mert a szinten minden csúcsnak van legalább fennmaradó hivatkozása, és nincs két 1. szintű csúcs nem lehet szomszédos, és nem lehetnek közösek a 2. szintű csúcsok, mivel ez a kerületnél rövidebb ciklust hozna létre. Általában a hasonló érvek azt mutatják, hogy minden szinten léteznie kell legalább csúcsoknak. Így a csúcsok teljes számának minimumnak kell lennie $G$ $d$ $2k+1$ $v$ $v$ $v$ $d$ $k>1$ $d(d-1)$ $l$ $d-1$ ${\displaystyle 1\leq {i}\leq {k))$ ${\displaystyle d(d-1)^{i))$

1+d\sum _{i=0}^{k-1}(d-1)^{i}.

A Moore-gráfban ezt a csúcsszámot elérjük. Minden Moore-gráfnak pontosan van kerülete – nincs elég csúcsa a nagyobb kerülethez, és egy rövidebb ciklus azt eredményezné, hogy egyes szélesség-első keresési fák első szintjein hiányoznak a csúcsok. Így minden Moore-gráfnak a lehető legkisebb számú csúcsa van az összes minimális fokszámú és átmérőjű gráf között - ez egy cella . $2k+1$ $k$ $d$ $k$

Egyenletes körmérethez az egyik él közepétől kiindulva alakítható ki egy hasonló szélesség-első keresőfa. Ennek a kerületnek a minimális fokszámú gráfjában megkapjuk a minimális csúcsszám korlátját $2k$ $d$

2\sum _{i=0}^{k-1}(d-1)^{i}=1+(d-1)^{k-1}+d\sum _{i=0 }^{k-2}(d-1)^{i}.

Így a Moore-gráfok olykor olyan gráfokat is tartalmaznak, amelyeken egy adott határt elérünk. Ismét minden ilyen gráf cella.

Példák

A Hoffman-Singleton tétel kimondja, hogy minden 5-ös kerületű Moore-gráfnak 2-es, 3-as, 7-es vagy 57-es fokozatúnak kell lennie. A Moore-gráfok a következők:

Teljes gráfok n > 2 csúcsával. (átmérő 1, kerület 3, fok n-1, sorrend ) ${\displaystyle K_{n))$ $n$
páratlan ciklusok . (átmérő , kerület , 2. fok, 2n+1 sorrend) $C_{2n+1}$ $n$ $2n+1$
Petersen gróf . (2-es átmérő, 5-ös kerület, 3-as fok, 10-es sorrend)
Hoffman-Singleton grófja . (2-es átmérő, 5-ös kerület, 7-es fok, 50-es sorrend)
Egy hipotetikus gráf, amelynek átmérője 2, kerülete 5, foka 57 és rendje 3250, jelenleg nem ismert, hogy létezik-e ilyen gráf.

Higman megmutatta, hogy a többi Moore-gráftól eltérően az ismeretlen gráf nem lehet csúcstranzitív . Machai és Sheeran később kimutatta, hogy egy ilyen gráf automorfizmusának sorrendje nem haladja meg a 375-öt.

A Moore-gráfok általánosított definíciójában, ahol az egyenletes kerület megengedett, a páros kerületű gráfok megfelelnek (esetleg degenerált) általánosított sokszögek előfordulási gráfjainak . Néhány példa a páros ciklusokra , a teljes kétrészes gráfokra négyes kerülettel, a Heawood-gráf 3-as fokú és 6-os kerülettel, valamint a Tutt-Coxeter-gráf 3- as és 8-as kerülettel. Ismeretes [5] [6] ), hogy minden Moore A fent felsoroltak kivételével a grafikonoknak 5, 6, 8 vagy 12 kerületűnek kell lenniük. A páros kerület esete az általánosított n-szögekre vonatkozó Feit-Higman lehetséges értékek tételéből következik. $C_{2n}$ ${\displaystyle K_{n,n))$ $n$

Lásd még

Méretprobléma - átmérő
A legnagyobb ismert grafikonok táblázata adott átmérőhöz és maximális fokhoz

Irodalom

Jernej Azarija, Sandi Klavžar. A Moore-gráfok és -ciklusok extrém gráfok a konvex ciklusokhoz // Journal of Graph Theory . - 2015. - T. 80 . – S. 34–42 . - doi : 10.1002/jgt.21837 .
Bollobas Béla. Modern gráfelmélet. - Springer-Verlag , 1998. - V. 184. - ( Diplomás szövegek matematikából ). .
E. Bannai, T. Ito. Véges Moore-gráfokon // Journal of the Faculty of Science, University of Tokyo. Szekta. 1A, matematika. - 1973. - T. 20 . – S. 191–208 . Archiválva az eredetiből 2012. április 24-én.
RM Damerell. A Moore-grafikonokról // Mathematical Proceedings of the Cambridge Philosophical Society. - 1973. - T. 74 . – S. 227–236 . - doi : 10.1017/S0305004100048015 .
Erdős Pál, Rényi Alfréd, T. Sos Vera. A gráfelméleti problémáról // Studia Sci. Math. Magyar.. - 1966. - T. 1 . – S. 215–235 . .
Alan J. Hoffman, Robert R. Singleton. Moore-gráfok 2-es és 3-as átmérővel // IBM Journal of Research and Development. - 1960. - V. 5 , sz. 4 . – S. 497–504 . - doi : 10.1147/rd.45.0497 .
Martin Macaj, Jozef Širan. A hiányzó Moore-gráf tulajdonságainak keresése // Lineáris algebra és alkalmazásai . - 2010. - T. 432 . – S. 2381–2398 . - doi : 10.1016/j.laa.2009.07.018 . .
Robert R. Singleton. Nincs szabálytalan Moore-gráf // American Mathematical Monthly . - 1968. - T. 75 , sz. 1 . – S. 42–43 . - doi : 10.2307/2315106 .

Linkek

Brouwer és Haemers: Spectra of graphs Archivált : 2017. október 3., a Wayback Machine -nél
Weisstein, Eric W. Moore Graph (angol) a Wolfram MathWorld webhelyén .
Weisstein, Eric W. Hoffman-Singleton tétel (angolul) a Wolfram MathWorld webhelyen .