Berilgan diametr va maksimal darajadagi ma'lum bo'lgan eng katta grafikalar jadvali - Table of the largest known graphs of a given diameter and maximal degree

Yilda grafik nazariyasi, daraja diametri muammosi mumkin bo'lgan eng kattasini topish muammosi grafik berilgan maksimal uchun daraja va diametri. The Mur bog'langan bunga cheklovlar qo'yadi, ammo ko'p yillar davomida ushbu sohadagi matematiklar aniqroq javobga qiziqishgan. Quyidagi jadval ushbu muammo bo'yicha dolzarb yutuqlarni keltirib chiqaradi (2-darajali holat bundan mustasno, bu erda eng katta grafikalar mavjud tsikllar tepalarning toq soni bilan).

Diametri yo'naltirilmagan yo'nalish bo'yicha ma'lum bo'lgan eng katta grafikalar buyurtmalar jadvali

Quyida eng taniqli grafikalar uchun vertex raqamlari jadvali (2008 yil oktyabr holatiga ko'ra) yo'naltirilmagan daraja diametri muammosi daraja grafigi uchun maksimal 3 ≤d ≤ 16 va diametri 2k ≤ 10. Ushbu jadvaldagi grafikalardan faqat bir nechtasi (qalin harflar bilan belgilangan) maqbul (ya'ni mumkin bo'lgan eng katta) ekanligi ma'lum. Qolganlari hozirgacha kashf etilgan eng kattalaridir va shu bilan Mur chegarasiga (tepalik to'plamining kattaligi bo'yicha) tartibida yaqinroq bo'lgan kattaroq grafigini topish ochiq muammo. Ba'zi umumiy qurilishlar qiymatlari bilan ma'lum d va k jadvalda ko'rsatilgan doiradan tashqarida.

k d	2	3	4	5	6	7	8	9	10
3	10	20	38	70	132	196	360	600	1250
4	15	41	98	364	740	1 320	3 243	7 575	17 703
5	24	72	212	624	2 772	5 516	17 030	57 840	187 056
6	32	111	390	1404	7 917	19 383	76 461	331 387	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 268	75 893	279 616	1 697 688	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	187	1 215	11 712	76 518	1 417 248	8 599 986	90 001 236	1 171 998 164	10 012 349 898
16	200	1 600	14 640	132 496	1 771 560	14 882 658	140 559 416	2 025 125 476	12 951 451 931

Quyidagi jadval yuqorida keltirilgan jadvaldagi ranglarning kalitidir:

Rang	Tafsilotlar
*	The Petersen va Hoffman – Singleton grafikalar.
*	Bunday bo'lmagan optimal grafikalar Mur grafikalari.
*	Jeyms Allrayt tomonidan topilgan grafik.
*	G. Wegner tomonidan topilgan grafik.
*	Geoffrey Exoo tomonidan topilgan grafikalar.
*	McKay-Miller-Shira grafikalari tomonidan topilgan Makkay, Miller va Shiras (1998)
*	J. Gomez tomonidan topilgan grafikalar.
*	Mitjana M. va Francesc Comellas tomonidan topilgan grafik. Ushbu grafik Maykl Sampels tomonidan mustaqil ravishda topilgan.
*	Fiol, MA va Yebra, J.L.A tomonidan topilgan grafik.
*	Francesc Comellas va J. Gomes tomonidan topilgan grafik.
*	G. Pineda-Villavicencio, J. Gomes tomonidan topilgan grafikalar, Mirka Miller va X. Peres-Rozes. Batafsil ma'lumot mualliflar tomonidan chop etilgan maqolada mavjud.
*	Eyal Loz tomonidan topilgan grafikalar. Qo'shimcha tafsilotlar Eyal Loz va Yozef Shirashning maqolasida keltirilgan.
*	Maykl Sampels tomonidan topilgan grafikalar.
*	Maykl J. Dinnin va Pol Xafner tomonidan topilgan grafikalar. Batafsil ma'lumot mualliflar tomonidan chop etilgan maqolada mavjud.
*	Topilgan grafik Marston Konder.

Adabiyotlar

• Xofman, Alan J.; Singleton, Robert R. (1960), "Diametri 2 va 3 bo'lgan Mur grafikalari" (PDF), IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147 / rd.45.0497, JANOB  0140437

• J. Dinnin, Maykl; Hafner, Pol R. (1994), "Daraja / diametr muammosi uchun yangi natijalar", Tarmoqlar, 24 (7): 359–367, arXiv:matematik / 9504214, doi:10.1002 / net.3230240702, S2CID  26375247

• Makkay, Brendan D.; Miller, Mirka; Sirax, Yozef (1998), "Ikkita diametrli va maksimal daraja berilgan katta grafikalar to'g'risida eslatma", Kombinatoriya nazariyasi jurnali, B seriyasi, 74 (4): 110–118, doi:10.1006 / jctb.1998.1828

• Miller, Mirka; Sirax, Jozef (2013), "Mur graflari va boshqalar: daraja / diametr muammosini o'rganish", Elektron kombinatorika jurnali, Dinamik tadqiqot D

• Pineda-Villavisensio, Gilyermo; Gomes, Xose; Miller, Mirka; Peres-Rozesd, Xebert (2006), "6-diametrning eng yangi grafikalari", Diskret matematikadagi elektron yozuvlar, 24: 153–160, doi:10.1016 / j.endm.2006.06.044

• Loz, Eyal; Shiráz, Jozef (2008), "Diametr diametri muammosidagi yangi rekord grafikalar" (PDF), Australasian Journal of Combinatorics, 41: 63–80

Tashqi havolalar

• Daraja diametri onlayn jadval.
• CombinatoricsWiki.org saytidagi daraja - diametr muammosi.
• Eyal Lozning Darajasi-Diametri muammolari sahifasi.
• Geoffrey Exoo's Diagrammaning yozuvlar jadvallari sahifasi.
• Gilyermo Pineda-Vilyavisensioniki Tadqiqot sahifasi.