केज (ग्राफ सिद्धांत)

टुट्टे (3,8)-केज.

लेखाचित्र सिद्धांत के गणित क्षेत्र में, केज एक नियमित लेखाचित्र होता है जिसमें इसकी परिधि (लेखाचित्र सिद्धांत) के लिए जितना संभव हो उतना कम कोणबिंदु (लेखाचित्र सिद्धांत) होता है।

औपचारिक रूप से, (r, g)-लेखाचित्र को एक लेखाचित्र (विच्छेद गणित) के रूप में परिभाषित किया गया है जिसमें प्रत्येक शीर्ष में यथार्थ r प्रतिवैस है, और जिसमें सबसे छोटे चक्र लेखाचित्र की लंबाई ठीक g है। एक (r, g)-केज (r, g)-लेखाचित्र है जिसमें सभी (r, g)-लेखाचित्र में सबसे कम संख्या में कोने होते हैं। (3, g)-केज को प्रायः g-केज कहा जाता है।

यह ज्ञात है कि (r, g)-लेखाचित्र के किसी भी संयोजन के लिए r ≥ 2 और g ≥ 3 उपस्थित है। इससे पता चलता है कि सभी (r, g)-केज उपस्थित हैं।

यदि मूर लेखाचित्र डिग्री के साथ r और परिधि g उपस्थित है, तो यह एक केज होना चाहिए। इसके अतिरिक्त, मूर लेखाचित्र के आकार की सीमाएं पिंजरों के लिए सामान्यीकृत होती हैं: विषम परिधि वाला कोई भी केज g कम से कम होना चाहिए

$1+r\sum _{i=0}^{(g-3)/2}(r-1)^{i}$

कोने, और कोई केज भी परिधि g के साथ कम से कम निम्न होना चाहिए

$2\sum _{i=0}^{(g-2)/2}(r-1)^{i}$

कोने। कोई (r, g)-लेखाचित्र सटीक रूप से इतने सारे कोने परिभाषा के अनुसार एक मूर लेखाचित्र है और इसलिए स्वचालित रूप से एक केज है।

किसी दिए गए संयोजन के लिए कई r और g केज उपस्थित हो सकते हैं। उदाहरण के लिए तीन गैर-समरूपी (3, 10)-केज हैं, प्रत्येक 70 शीर्षों के साथ: बलबन 10-केज, हैरी लेखाचित्र और हैरीज़-वोंग लेखाचित्र। लेकिन एक ही (3, 11)-केज है : बलबन 11-केज (112 सिरों के साथ)।

ज्ञात केज

एक 1-नियमित लेखाचित्र में कोई चक्र नहीं होता है, और एक आनुषंगिक 2-नियमित लेखाचित्र में उसके शीर्षों की संख्या के बराबर परिधि होती है, इसलिए केज केवल r ≥ 3 के लिए रुचि के होते हैं। (r,3)-केज एक पूर्ण लेखाचित्र K_r+1 है r+1 कोने पर, और (r,4)-केज 2r शीर्ष पर एक पूर्ण द्विदलीय लेखाचित्र K_r,r है।

उल्लेखनीय पिंजरों में सम्मिलित हैं:

• (3,5)-केज: पीटरसन लेखाचित्र, 10 कोने
• (3,6)-केज: हीवुड लेखाचित्र, 14 कोने
• (3,7)-केज: मैगी लेखाचित्र , 24 शीर्ष
• (3,8)-केज: टुट्टे-कॉक्सेटर लेखाचित्र, 30 कोने
• (3,10)-केज: बलबन 10-केज, 70 कोने
• (3,11)-केज: बलबन 11-केज, 112 कोने
• (4,5)-केज: रॉबर्टसन लेखाचित्र, 19 कोने
• (7,5)-केज: हॉफमैन-सिंगलटन लेखाचित्र, 50 कोने।
• जब r − 1 एक प्रमुख शक्ति होती है, (r,6) केज प्रक्षेपी समतल के आपतन लेखाचित्र हैं।
• जब r − 1 एक प्रमुख शक्ति होती है, (r,8) और (r,12) केज सामान्यीकृत बहुभुज हैं।

ज्ञात (r, g) पिंजरों में कोने की संख्या, r> 2 और g> 2 के मूल्यों के लिए, प्रक्षेपी समतल और सामान्यीकृत बहुभुजों के अतिरिक्त, हैं:

g r	3	4	5	6	7	8	9	10	11	12
3	4	6	10	14	24	30	58	70	112	126
4	5	8	19	26	67	80				728
5	6	10	30	42		170				2730
6	7	12	40	62		312				7812
7	8	14	50	90

अनंतस्पर्शी

g के बड़े मूल्यों के लिए, मूर बाउंड का तात्पर्य है कि कोने की संख्या कम से कम घातीय वृद्धि होनी चाहिए। समान रूप से, g, n के लघुगणक के अधिक से अधिक समानुपाती हो सकता है। अधिक यथार्थतः,

$g\leq 2\log _{r-1}n+O(1).$

ऐसा माना जाता है कि यह बन्ध तंग या तंग (बोलोबस & ज़ेमेरीडी 2002) के करीब है। g पर सबसे अच्छी ज्ञात निचली सीमाएँ भी लघुगणकीय हैं, लेकिन एक छोटे स्थिर कारक के साथ (जिसका अर्थ है कि n अकेले घातीय रूप से बढ़ता है लेकिन मूर बाध्य की तुलना में उच्च दर पर)। विशेष रूप से, द्वारा परिभाषित रामानुजन रेखांकन का निर्माण लुबोत्ज़की, फिलिप्स & सरनाक (1988) सीमा को संतुष्ट करते हैं

$g\geq {\frac {4}{3}}\log _{r-1}n+O(1).$

लेज़ेबनिक, उस्तिमेंको & वोल्डर (1995) द्वारा इस सीमा में थोड़ा सुधार किया गया था।

यह संभावना नहीं है कि ये रेखांकन स्वयं केज हैं, लेकिन उनका अस्तित्व एक केज में आवश्यक शीर्षों की संख्या के लिए एक ऊपरी सीमा प्रदान करता है।

संदर्भ

• Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge Mathematical Library, pp. 180–190, ISBN 0-521-45897-8.
• Bollobás, Béla; Szemerédi, Endre (2002), "Girth of sparse graphs", Journal of Graph Theory, 39 (3): 194–200, doi:10.1002/jgt.10023, MR 1883596.
• Exoo, G; Jajcay, R (2008), "Dynamic Cage Survey", Dynamic Surveys, Electronic Journal of Combinatorics, DS16, archived from the original on 2015-01-01, retrieved 2012-03-25.
• Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235, archived from the original (PDF) on 2016-03-09, retrieved 2010-02-23.
• Hartsfield, Nora; Ringel, Gerhard (1990), Pearls in Graph Theory: A Comprehensive Introduction, Academic Press, pp. 77–81, ISBN 0-12-328552-6.
• Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, pp. 183–213, ISBN 0-521-43594-3.
• Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J. (1995), "A new series of dense graphs of high girth", Bulletin of the American Mathematical Society, New Series, 32 (1): 73–79, arXiv:math/9501231, doi:10.1090/S0273-0979-1995-00569-0, MR 1284775.
• Lubotzky, A.; Phillips, R.; Sarnak, P. (1988), "Ramanujan graphs", Combinatorica, 8 (3): 261–277, doi:10.1007/BF02126799, MR 0963118.
• Tutte, W. T. (1947), "A family of cubical graphs", Proc. Cambridge Philos. Soc., 43 (4): 459–474, Bibcode:1947PCPS...43..459T, doi:10.1017/S0305004100023720.

बाहरी संबंध

• Brouwer, Andries E. Cages
• Royle, Gordon. Cubic Cages and Higher valency cages
• Weisstein, Eric W. "Cage Graph". MathWorld.