नेसर ग्राफ

For यूनिमॉड्यूलर लैटिस का नेसर नेबरहुड ग्राफ, see नीमेयर जाली.

केसर ग्राफ
230पीएक्स नेसर ग्राफ K(5, 2), पीटरसन ग्राफ के समरूपी
Named after	मार्टिन केसर
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}</math>-नियमित चाप-संक्रमणीय
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}},$ प्रति शीर्ष पड़ोसियों की संख्या के समान होती है।

रंगीन संख्या

जैसा कनेसर (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 अलग-अलग आइजन मूल्य ​​​​सम्मिलित हैं:

$$\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) डेसरगुएस ग्राफ और द्विदलीय कनेसर ग्राफ है 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), "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.