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

ऑल (3,8)-cage.

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

औपचारिक रूप से, ए (r, g)-graph को एक ग्राफ़ (विच्छेद गणित) के रूप में परिभाषित किया गया है जिसमें प्रत्येक शीर्ष में सटीक है r पड़ोसी, और जिसमें सबसे छोटे चक्र ग्राफ की लंबाई ठीक है g. एक (r, g)-cage एक (r, g)-graph सबसे कम संभव शीर्षों के साथ, सभी के बीच (r, g)-graphs. ए (3, g)-cage को अक्सर कहा जाता है g-cage.

यह ज्ञात है कि ए (r, g)-graph के किसी भी संयोजन के लिए मौजूद है r ≥ 2 और g ≥ 3. यह सब इस प्रकार है (r, g)-cages अस्तित्व।

यदि मूर ग्राफ डिग्री के साथ मौजूद है 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)-graph सटीक रूप से इतने सारे कोने परिभाषा के अनुसार एक मूर ग्राफ है और इसलिए स्वचालित रूप से एक पिंजरा है।

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

ज्ञात पिंजरे

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

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

• (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) पिंजरे सामान्यीकृत बहुभुज हैं।

ज्ञात (आर, जी) पिंजरों में कोने की संख्या, आर> 2 और जी> 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, n के लघुगणक के अधिक से अधिक समानुपाती हो सकता है। ज्यादा ठीक,

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

ऐसा माना जाता है कि यह बन्ध तंग या तंग के करीब है (Bollobás & Szemerédi 2002). जी पर सबसे अच्छी ज्ञात निचली सीमाएँ भी लॉगरिदमिक हैं, लेकिन एक छोटे स्थिर कारक के साथ (जिसका अर्थ है कि एन अकेले घातीय रूप से बढ़ता है लेकिन मूर बाउंड की तुलना में उच्च दर पर)। विशेष रूप से, द्वारा परिभाषित रामानुजन रेखांकन का निर्माण Lubotzky, Phillips & Sarnak (1988) सीमा को पूरा करें

$g\geq {\frac {4}{3}}\log _{r-1}n+O(1).$ द्वारा इस सीमा में थोड़ा सुधार किया गया था Lazebnik, Ustimenko & Woldar (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.