कनेसर ग्राफ

For the Kneser neighborhood graph of unimodular lattices, see Niemeier lattice.

Kneser graph
The Kneser graph K(5, 2), isomorphic to the Petersen graph
Named after	Martin Kneser
Vertices	${\binom {n}{k}}$
Edges	${\frac {1}{2}}{\binom {n}{k}}{\binom {n-k}{k}}$
Chromatic number	${\begin{cases}n-2k+2&n\geq 2k\\1&n<2k\end{cases}}$
Properties	${\tbinom {n-k}{k}}$-regular arc-transitive
Notation	K(n, k), KGn,k.
Table of graphs and parameters

ग्राफ़ सिद्धांत में, केनेसर ग्राफ़ K(n, k) (वैकल्पिक रूप से KG_n,k) वह ग्राफ है जिसके शीर्ष संयोजन के अनुरूप हैं|k-एक सेट के तत्व उपसमुच्चय n तत्व, और जहां दो शीर्ष आसन्न हैं यदि और केवल यदि दो संगत असंयुक्त सेट हैं। कनेसर ग्राफ़ का नाम मार्टिन कनेसर के नाम पर रखा गया है, जिन्होंने पहली बार 1956 में उनकी जांच की थी।

उदाहरण

कनेसर ग्राफ O₄ = K(7, 3)

कनेसर ग्राफ K(n, 1) पूरा ग्राफ़ है n शिखर.

कनेसर ग्राफ K(n, 2) संपूर्ण ग्राफ़ के लाइन ग्राफ़ का पूरक ग्राफ़ है n शिखर.

कनेसर ग्राफ K(2n − 1, n − 1) विषम ग्राफ है O_n; विशेष रूप से O₃ = K(5, 2) पीटरसन ग्राफ है (ऊपर दाईं ओर का चित्र देखें)।

कनेसर ग्राफ O₄ = K(7, 3), दाहिनी ओर देखा गया।

गुण

मूल गुण

कनेसर ग्राफ $K(n,k)$ है ${\tbinom {n}{k}}$ शिखर. प्रत्येक शीर्ष पर बिल्कुल वैसा ही है ${\tbinom {n-k}{k}}$ पड़ोसियों।

नेसर ग्राफ शीर्ष-संक्रमणीय ग्राफ और सममित ग्राफ है। कब $k=2$, केन्सर ग्राफ़ मापदंडों के साथ एक दृढ़ता से नियमित ग्राफ़ है $({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{2}})$. हालाँकि, यह दृढ़ता से नियमित नहीं है जब $k>2$, क्योंकि गैर-आसन्न शीर्षों के विभिन्न युग्मों में समुच्चय के संगत युग्मों के प्रतिच्छेदन के आकार के आधार पर समान पड़ोसियों की संख्या भिन्न-भिन्न होती है।

चूँकि केन्सर ग्राफ़ नियमित ग्राफ़ और किनारे-संक्रमणीय ग्राफ़|किनारे-संक्रमणीय होते हैं, उनका के-वर्टेक्स-कनेक्टेड ग्राफ़ उनकी डिग्री (ग्राफ़ सिद्धांत) के बराबर होता है, सिवाय इसके कि $K(2k,k)$ जो डिसकनेक्ट हो गया है. अधिक सटीक रूप से, की कनेक्टिविटी $K(n,k)$ है ${\tbinom {n-k}{k}},$ प्रति शीर्ष पड़ोसियों की संख्या के समान।

वर्णिक संख्या

जैसा Kneser (1956) अनुमानित, केनेसर ग्राफ की रंगीन संख्या $K(n,k)$ के लिए $n\geq 2k$ बिलकुल है n − 2k + 2; उदाहरण के लिए, पीटरसन ग्राफ़ को किसी भी उचित रंग में तीन रंगों की आवश्यकता होती है। यह अनुमान कई प्रकार से सिद्ध हुआ।

• लास्ज़लो लोवेज़ ने 1978 में टोपोलॉजिकल तरीकों का उपयोग करके इसे साबित किया, टोपोलॉजिकल कॉम्बिनेटरिक्स के क्षेत्र को जन्म दे रहा है।
• इसके तुरंत बाद इमरे बरनी ने बोरसुक-उलम प्रमेय और डेविड गेल की एक लेम्मा का उपयोग करते हुए एक सरल प्रमाण दिया।
• जोशुआ ई. ग्रीन ने अपने और अधिक सरलीकृत लेकिन फिर भी टोपोलॉजिकल प्रमाण के लिए उत्कृष्ट स्नातक अनुसंधान के लिए 2002 का मॉर्गन पुरस्कार जीता।
• 2004 में, जिरी माटूसेक (गणितज्ञ)|जिरी माटौसेक को एक विशुद्ध रूप से मिश्रित प्रमाण मिला।

इसके विपरीत, इन ग्राफ़ों की भिन्नात्मक वर्णिक संख्या है $n/k$. कब $n<2k$, $K(n,k)$ इसका कोई किनारा नहीं है और इसकी वर्णिक संख्या 1 है।

हैमिल्टनियन चक्र

कनेसर ग्राफ K(n, k) में एक हैमिल्टनियन चक्र शामिल है यदि

$$n\geq {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right).$$

तब से

$${\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right)<\left({\frac {3+{\sqrt {5}}}{2}}\right)k+1$$

सभी के लिए धारण करता है $k$ यह शर्त संतुष्ट है यदि

$$n\geq \left({\frac {3+{\sqrt {5}}}{2}}\right)k+1\approx 2.62k+1.$$

कनेसर ग्राफ K(n, k) में एक हैमिल्टनियन चक्र शामिल है यदि कोई गैर-नकारात्मक पूर्णांक मौजूद है $n=2k+2^{a}$. विशेष रूप से, विषम ग्राफ़ O_n के पास हैमिल्टनियन चक्र है यदि n ≥ 4. पीटरसन ग्राफ़ के अपवाद के साथ, सभी कनेक्टेड केनेसर ग्राफ़ K(n, k) साथ n ≤ 27 हैमिल्टनियन हैं।

क्लिक्स

कब n < 3k, कनेसर ग्राफ K(n, k) में कोई त्रिभुज नहीं है. अधिक सामान्यतः, जब n < ck इसमें आकार का क्लिक (ग्राफ सिद्धांत) शामिल नहीं है c, जबकि इसमें ऐसे समूह शामिल होते हैं जब n ≥ ck. इसके अलावा, हालांकि केन्सर ग्राफ में हमेशा लंबाई चार का चक्र (ग्राफ सिद्धांत) होता है n ≥ 2k + 2, के मूल्यों के लिए n के करीब 2k सबसे छोटे विषम चक्र की लंबाई परिवर्तनशील हो सकती है।

व्यास

कनेक्टेड केनेसर ग्राफ की दूरी (ग्राफ़ सिद्धांत)। K(n, k) है

$$\left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.$$

स्पेक्ट्रम

कनेसेर ग्राफ का ग्राफ स्पेक्ट्रम K(n, k) k + 1 विशिष्ट eigenvalues ​​​​से मिलकर बनता है:

$$\lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}},\qquad j=0,\ldots ,k.$$

इसके अतिरिक्त $\lambda _{j}$ बहुलता (गणित) के साथ होता है ${\tbinom {n}{j}}-{\tbinom {n}{j-1}}$ के लिए $j>0$ और $\lambda _{0}$ बहुलता 1 है.

स्वतंत्रता संख्या

एर्दो-को-राडो प्रमेय में कहा गया है कि केन्सर ग्राफ की स्वतंत्रता संख्या K(n, k) के लिए $n\geq 2k$ है

$$\alpha (K(n,k))={\binom {n-1}{k-1}}.$$

संबंधित ग्राफ़

जॉनसन ग्राफ J(n, k) वह ग्राफ है जिसके शीर्ष हैं k-ए के तत्त्व उपसमुच्चय n-तत्व समुच्चय, जब दो शीर्ष एक में मिलते हैं तो आसन्न होते हैं (k − 1)-तत्व सेट. जॉनसन ग्राफ J(n, 2) नेसर ग्राफ का पूरक ग्राफ है K(n, 2). जॉनसन ग्राफ़ जॉनसन योजना से निकटता से संबंधित हैं, दोनों का नाम सेल्मर एम. जॉनसन के नाम पर रखा गया है।

सामान्यीकृत कनेसर ग्राफ K(n, k, s) का नेसर ग्राफ़ के समान ही शीर्ष सेट है K(n, k), लेकिन दो शीर्षों को जोड़ता है जब भी वे उन सेटों के अनुरूप होते हैं जो एक दूसरे को काटते हैं s या कम आइटम। इस प्रकार K(n, k, 0) = K(n, k).

द्विदलीय कनेसर ग्राफ H(n, k) के शीर्षों के समुच्चय हैं k और n − k के संग्रह से ली गई वस्तुएँ nतत्व. जब भी एक सेट दूसरे का उपसमुच्चय होता है तो दो शीर्ष एक किनारे से जुड़े होते हैं। नेसर ग्राफ की तरह यह डिग्री के साथ शीर्ष परिवर्तनीय है ${\tbinom {n-k}{k}}.$ द्विदलीय कनेसेर ग्राफ को द्विदलीय दोहरे आवरण के रूप में बनाया जा सकता है K(n, k) जिसमें प्रत्येक शीर्ष की दो प्रतियां बनाई जाती हैं और प्रत्येक किनारे को शीर्षों के संगत जोड़े को जोड़ने वाले किनारों की एक जोड़ी से बदल दिया जाता है। द्विदलीय कनेसर ग्राफ H(5, 2) Desargues ग्राफ और द्विदलीय कनेसर ग्राफ़ है H(n, 1) एक ताज ग्राफ है.

संदर्भ

उद्धृत कार्य

• Bárány, Imre (1978), "A short proof of Kneser's conjecture", Journal of Combinatorial Theory, Series A, 25 (3): 325–326, doi:10.1016/0097-3165(78)90023-7, MR 0514626
• Chen, Ya-Chen (2003), "Triangle-free Hamiltonian Kneser graphs", Journal of Combinatorial Theory, Series B, 89 (1): 1–16, doi:10.1016/S0095-8956(03)00040-6, MR 1999733
• Denley, Tristan (1997), "The odd girth of the generalised Kneser graph", European Journal of Combinatorics, 18 (6): 607–611, doi:10.1006/eujc.1996.0122, MR 1468332
• Godsil, Christopher; Meagher, Karen (2015), Erdős–Ko–Rado Theorems: Algebraic Approaches, Cambridge Studies in Advanced Mathematics, Cambridge University Press, p. 43, ISBN 9781107128446

• Greene, Joshua E. (2002), "A new short proof of Kneser's conjecture", American Mathematical Monthly, 109 (10): 918–920, doi:10.2307/3072460, JSTOR 3072460, MR 1941810
• Kneser, Martin (1956), "Aufgabe 360", Jahresbericht der Deutschen Mathematiker-Vereinigung, 58 (2): 27
• Lovász, László (1978), "Kneser's conjecture, chromatic number, and homotopy", Journal of Combinatorial Theory, Series A, 25 (3): 319–324, doi:10.1016/0097-3165(78)90022-5, hdl:10338.dmlcz/126050, MR 0514625
• Matoušek, Jiří (2004), "A combinatorial proof of Kneser's conjecture", Combinatorica, 24 (1): 163–170, doi:10.1007/s00493-004-0011-1, hdl:20.500.11850/50671, MR 2057690, S2CID 42583803
• Mütze, Torsten; Nummenpalo, Jerri; Walczak, Bartosz (2021) [STOC 2018], "Sparse Kneser graphs are Hamiltonian", Journal of the London Mathematical Society, New York, 103 (4): 912–919, arXiv:1711.01636, doi:10.1112/jlms.12406, MR 3826304
• Shields, Ian Beaumont (2004), Hamilton Cycle Heuristics in Hard Graphs, Ph.D. thesis, North Carolina State University, archived from the original on 2006-09-17, retrieved 2006-10-01
• Simpson, J. E. (1991), "Hamiltonian bipartite graphs", Proceedings of the Twenty-Second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Congressus Numerantium, vol. 85, pp. 97–110, MR 1152123
• Valencia-Pabon, Mario; Vera, Juan-Carlos (2005), "On the diameter of Kneser graphs", Discrete Mathematics, 305 (1–3): 383–385, doi:10.1016/j.disc.2005.10.001, MR 2186709
• Watkins, Mark E. (1970), "Connectivity of transitive graphs", Journal of Combinatorial Theory, 8: 23–29, doi:10.1016/S0021-9800(70)80005-9, MR 0266804

बाहरी संबंध

• Weisstein, Eric W. "Kneser Graph". MathWorld.
• Weisstein, Eric W. "Odd Graph". MathWorld.