A matematika, azon belül a gráfelmélet területén az 1960-as évek óta vizsgált fokszám-átmérő probléma (degree diameter problem) vagy (∆,D)-probléma annak a V csúcshalmaz mérete szerinti lehető legnagyobb G gráf megkeresésének problémája, melynek átmérője k, fokszáma pedig legfeljebb d. A G méretének felső korlátját a Moore-gráfok adják; 1 < k és 2 < d paraméterek mellett csak a Petersen-gráf, a Hoffman–Singleton-gráf és létezése esetén egy k = 2 átmérőjű és d = 57 fokszámú gráf éri el a Moore-korlátot. Általában a legnagyobb, adott fokszámú és átmérőjű gráfok sokkal kisebbek a Moore-korlátnál.

Képlet Ha az adott d fokszám és k átmérő mellett elérhető maximális csúcsszám, akkor , ahol a Moore-korlát:

Az egyenlőség nagyon kevés gráf esetében teljesül, ezért inkább azt érdemes vizsgálni, hogy a Moore-korláthoz mennyire közel létezhetnek gráfok. Vizsgálták a (∆, D, −δ)-gráfokat, tehát a legfeljebb D átmérőjű, ∆ maximális fokszámú gráfok, melyek δ defektussal maradnak el a Moore-korláttól – elsősorban a −1 és −2 defektusokat.

Az aszimptotikus viselkedés vizsgálatához megjegyzendő, hogy .

Különböző gráfosztályok A fokszám-átmérő problémát irányítatlan gráfok mellett irányított gráfokon és vegyes gráfokon is megvizsgálták.

Irányítatlan gráfok Az irányítatlan gráfokon belül a következő gráfosztályokat vizsgálták meg: csúcstranzitív gráfok, Cayley-gráfok, Abel-csoportok Cayley-gráfjai; páros gráfok; különböző felületekbe ágyazott (síkbarajzolható, tóruszra rajzolható) gráfok.

Irányított gráfok Irányított gráfok esetében csak triviális (d=1 vagy k=1) Moore-digráfok léteznek.W.G. Bridges and S. Toueg, On the impossibility of directed Moore graphs, J.Combinatorial Theory B 29 (1980) 339–341

Az irányított gráfokon belül a következő gráfosztályokat vizsgálták meg: csúcstranzitív gráfok, Cayley-gráfok; síkbarajzolható gráfok.

Vegyes gráfok Az irányított, illetve irányítatlan Moore-gráfok felfoghatók az általánosabb vegyes („részben irányított”) Moore-gráfok speciális eseteiként.

Kapcsolódó problémák BollobásB. Bollobás, Extremal Graph Theory, Academic Press, New York (1978). hasonló jellegű problémát vetett fel: adott átmérő és maximális fokszám mellett keressük meg a lehetséges legkevesebb élű gráfot. Gómez és EscuderoJ. Gómez and M. Escudero, Optimal edge coloring of large graphs, Networks 34 (1999) 61–65. megvizsgálták az olyan gráfok konstruálásának lehetőségeit, melyek sok csúccsal, adott D átmérővel és ∆ maximális fokszámmal rendelkeznek, továbbá éleiket pontosan p színnel lehet színezni. Táblázatukban megadják az ilyen irányított gráfokat a D ≤ 10 és p ≤ 16 esetekre.

Fokszám/bőség probléma: adott d > 2 és g > 3 természetes számokra keressük meg a legkevesebb csúcsú reguláris gráfot, melynek fokszáma d, girthparamétere (bősége) g. Rend/fokszám probléma: adott n és ∆ természetes számok, keressük meg a lehetséges legkisebb Dn,∆ átmérőt egy n rendű és ∆ maximális fokszámú gráfban. Rend/átmérő probléma: adott n és D természetes számok, keressük meg a lehetséges legkisebb ∆n,D maximális fokszámot egy n rendű és D átmérőjű gráfban. A fenti problémák irányított változatában fokszám helyett ki-fokszám szerepel. adott n, D, D′ és s, határozzuk meg az n csúcsú, D átmérőjű gráf éleinek minimális számát, ha tudjuk, hogy a gráfból s vagy kevesebb él eltávolítása után legfeljebb D′ átmérőjű gráfot kapunk MaxDDBS probléma: adott irányítatlan összefüggő G gráf, keressük a legnagyobb összefüggő S részgráfot, melynek maximális fokszáma ≤ ∆ és átmérője ≤ D. Kellően nagy teljes gráfot választva G-nek látható, hogy ennek a problémának egyik speciális esete a fokszám-átmérő probléma.

Ismert korlátok

Az irányítatlan fokszám-átmérő probléma legnagyobb ismert gráfjainak rendjei Keressük az adott maximális fokszám és átmérő mellett lehetséges legnagyobb irányítatlan gráf csúcsainak számát (rendjét). A Moore-korlát felső határt szab a csúcsok számának, de a matematikusok ennél precízebb választ keresnek. Az alábbi táblázat bemutatja a probléma jelenlegi állását (nem számítva a 2 fokszám esetét, ahol a legnagyobb gráfok a páratlan számú csúcsból álló körök, és a triviális ∆ = 1, D = 1 esetet).

Az alábbi táblázatban találhatók a legnagyobb (2008 októberében) ismert gráfok csúcsszámai az irányítatlan fokszám-átmérő problémára, 3 ≤ d ≤ 16 fokszámra és 2 ≤ k ≤ 10 átmérőre. A táblázatban csak néhány gráf optimális (aláhúzással jelölve), tehát a lehetséges legnagyobb. A többi szám csak az eddig felfedezett legnagyobb gráfot jelenti, tehát a Moore-korláthoz közelebb álló, nagyobb gráf keresése ezeknél nyitott kérdés. A táblázat d és k értékein kívül eső számokra is ismertek konstrukciók. 2 3 4 5 6 7 8 9 10 3 10 20 38 70 132 196 336 600 1250 4 15 41 96 364 740 1 320 3 243 7 575 17 703 5 24 72 210 624 2 772 5 516 17 030 57 840 187 056 6 32 110 390 1404 7 917 19 383 76 461 307 845 1 253 615 7 50 168 672 2 756 11 988 52 768 249 660 1 223 050 6 007 230 8 57 253 1 100 5 060 39 672 131 137 734 820 4 243 100 24 897 161 9 74 585 1 550 8 200 75 893 279 616 1 686 600 12 123 288 65 866 350 10 91 650 2 286 13 140 134 690 583 083 4 293 452 27 997 191 201 038 922 11 104 715 3 200 19 500 156 864 1 001 268 7 442 328 72 933 102 600 380 000 12 133 786 4 680 29 470 359 772 1 999 500 15 924 326 158 158 875 1 506 252 500 13 162 851 6 560 40 260 531 440 3 322 080 29 927 790 249 155 760 3 077 200 700 14 183 916 8 200 57 837 816 294 6 200 460 55 913 932 600 123 780 7 041 746 081 15 186 1 215 11 712 76 518 1 417 248 8 599 986 90 001 236 1 171 998 164 10 012 349 898 16 198 1 600 14 640 132 496 1 771 560 14 882 658 140 559 416 2 025 125 476 12 951 451 931

A táblázat színkódjait a következőképpen lehet értelmezni:

Szín Részletek * A Petersen- és a Hoffman–Singleton-gráf. * Optimális gráfok, melyek nem Moore-gráfok. * James Allwright által megtalált gráf. * G. Wegner által megtalált gráf. * Graphs found by Geoffrey Exoo által megtalált gráf. * Brendan D. McKay, Mirka Miller és Jozef Širáň által megtalált gráfcsalád. További részletek a szerzők tanulmányában. * J. Gómez által megtalált gráf. * Mitjana M. és Francesc Comellas által megtalált gráf. Tőlük függetlenül Michael Sampels is megtalálta. * Fiol, M.A. és Yebra, J.L.A által megtalált gráf. * Francesc Comellas és J. Gómez által megtalált gráf. * Brendan D. McKay, Mirka Miller és Jozef Širáň által megtalált gráfcsalád. További részletek a szerzők tanulmányában. * Eyal Loz által megtalált gráfok. További részletek Eyal Loz és Jozef Širáň tanulmányában. * Michael Sampels által megtalált gráfok. * Michael J. Dinneen és Paul Hafner által megtalált gráfok. További részletek a szerzők tanulmányában. * Marston Conder által megtalált gráf.

Az irányított fokszám-átmérő probléma legnagyobb ismert csúcsszimmetrikus gráfjainak rendjei Az alábbi táblázatban találhatók a legnagyobb (2008 októberében) ismert gráfok csúcsszámai az irányított fokszám-átmérő problémára, a csúcstranzitív digráfokra szűkítve, 2 ≤ d ≤ 13 fokszámra és 2 ≤ k ≤ 11 átmérőre.

2 3 4 5 6 7 8 9 10 11 2 6 10 20 27 72 144 171 336 504 737 3 12 27 60 165 333 1 152 2 041 5 115 11 568 41 472 4 20 60 168 465 1 378 7 200 14 400 42 309 137 370 648 000 5 30 120 360 1 152 3 775 28 800 86 400 259 200 1 010 658 5 184 000 6 42 210 840 2 520 9 020 88 200 352 800 1 411 200 5 184 000 27 783 000 7 56 336 1 680 6 720 20 160 225 792 1 128 960 5 644 800 27 783 000 113 799 168 8 72 504 3 024 15 120 60 480 508 032 3 048 192 18 289 152 113 799 168 457 228 800 9 90 720 5 040 30 240 151 200 1 036 800 7 257 600 50 803 200 384 072 192 1 828 915 200 10 110 990 7 920 55 400 332 640 1 960 200 15 681 600 125 452 800 1 119 744 000 6 138 320 000 11 132 1 320 11 880 95 040 665 280 3 991 680 31 152 000 282 268 800 2 910 897 000 18 065 203 200 12 156 1 716 17 160 154 440 1 235 520 8 648 640 58 893 120 588 931 200 6 899 904 000 47 703 427 200 13 182 2 184 24 024 240 240 2 162 160 17 297 280 121 080 960 1 154 305 152 15 159 089 098 115 430 515 200

A táblázat színkódjait a következőképpen lehet értelmezni:

Szín Részletek * W.H.Kautz által megtalált gráfcsalád. További részletek a szerző tanulmányában. * V.Faber és J.W.Moore által megtalált gráfcsalád. További részletek más szerzőktől is hozzáférhetők. * V.Faber és J.W.Moore által megtalált gráf. A rendhez tartozó összes Cayley-digráfot Eyal Loz találta meg. * Francesc Comellas és M. A. Fiol által megtalált digráfok. További részletek a szerzők tanulmányában. * Michael J. Dinneen által megtalált Cayley-digráfok. További részletek a szerző tanulmányában. * Michael J. Dinneen által megtalált Cayley-digráfok. A rendhez tartozó összes Cayley-digráfot Eyal Loz találta meg. * Paul Hafner által megtalált Cayley-digráfok. További részletek a szerző tanulmányában. * Paul Hafner által megtalált Cayley-digráfok. A rendhez tartozó összes Cayley-digráfot Eyal Loz találta meg. * J. Gómez által megtalált digráfok. * Eyal Loz által megtalált Cayley-digráfok. További részletek Eyal Loz és Jozef Širáň tanulmányában.

Kapcsolódó szócikkek Cage (gráfelmélet) Részgráf fokszám-átmérő problémája (MaxDDBS)

Fordítás

Jegyzetek

További információk Vertex-symmetric Digraphs online table. The Degree - Diameter Problem on CombinatoricsWiki.org. Eyal Loz's Degree-Diameter problem page.

Kategória:Számítási problémák a gráfelméletben