सर्कुलेंट ग्राफ

ऑर्डर 13 का पाले ग्राफ, सर्कुलेंट ग्राफ का उदाहरण।

ग्राफ सिद्धांत में, सर्कुलेंट ग्राफ एक अप्रत्यक्ष ग्राफ होता है, जो ग्राफ ऑटोमोर्फिज्म के चक्रीय समूह द्वारा क्रियान्वित होता है, जो शीर्ष-सकर्मक ग्राफ होता है। इसे कभी-कभी चक्रीय ग्राफ कहा जाता है,^[1]लेकिन इस शब्द के अन्य अर्थ हैं।

समतुल्य परिभाषाएँ

सर्कुलेंट ग्राफ़ को कई समान तरीकों से वर्णित किया जा सकता है:^[2]

ग्राफ़ के ऑटोमॉर्फिज़्म समूह में एक चक्रीय समूह उपसमूह शामिल होता है जो ग्राफ़ के शीर्ष पर समूह क्रिया (गणित) करता है। दूसरे शब्दों में, ग्राफ़ में एक ग्राफ़ ऑटोमोर्फिज्म समूह, जो इसके शीर्षों का चक्रीय क्रमचय है।
ग्राफ़ में एक आसन्न मैट्रिक्स है जो एक मैट्रिक्स की परिक्रमा है।
$n}$ ग्राफ़ के शीर्षों को 0 से लेकर तक क्रमांकित किया जा सकता है $n - 1$ इस तरह से कि, यदि कुछ दो शीर्षों को क्रमांकित किया गया है $x$ और $(x + d) mod n$ सन्निकट हैं, तो प्रत्येक दो शीर्षों को क्रमांकित किया गया है $z$ और $(z + d) mod n$ सटे हुए हैं।
ग्राफ़ खींचा जा सकता है (संभवतः क्रॉसिंग के साथ) ताकि इसके कोने एक नियमित बहुभुज के कोनों पर स्थित हों, और बहुभुज की प्रत्येक घूर्णी समरूपता भी आरेखण की एक समरूपता है।
ग्राफ एक चक्रीय समूह का केली ग्राफ है।^[3]

उदाहरण

हर चक्र ग्राफ एक सर्कुलेंट ग्राफ है, जैसा कि हर क्राउन ग्राफ के साथ होता है 2 modulo 4 शिखर।

आदेश के पाले रेखांकन $n$ (कहाँ $n$ के सर्वांगसम अभाज्य संख्या है 1 modulo 4) एक ग्राफ़ है जिसमें शीर्ष 0 से संख्याएँ हैं $n - 1$ और दो कोने आसन्न हैं यदि उनका अंतर एक द्विघात अवशेष मॉड्यूलो है $n$ . चूंकि किनारे की उपस्थिति या अनुपस्थिति केवल अंतर मॉड्यूलो पर निर्भर करती है $n$ दो शीर्ष संख्याओं का, कोई भी पाले ग्राफ एक सर्कुलेंट ग्राफ है।

प्रत्येक मोबियस सीढ़ी एक गोलाकार ग्राफ है, जैसा कि प्रत्येक पूर्ण ग्राफ है। एक पूर्ण द्विदलीय ग्राफ एक सर्कुलेंट ग्राफ है यदि इसके द्विभाजन के दोनों ओर समान संख्या में कोने हैं।

अगर दो नंबर $m$ और $n$ अपेक्षाकृत प्रमुख हैं, तो $m \times n$ रूक का ग्राफ़ (एक ग्राफ़ जिसमें प्रत्येक वर्ग के लिए एक वर्टेक्स होता है $m \times n$ शतरंज की बिसात और प्रत्येक दो वर्गों के लिए एक किनारा जिसे एक शतरंज का बदमाश एक ही चाल में चला सकता है) एक गोलाकार ग्राफ है। ऐसा इसलिए है क्योंकि इसकी समरूपता में उपसमूह के रूप में चक्रीय समूह सी शामिल है_mn $\simeq$ सी_m×C_n. अधिक आम तौर पर, इस मामले में, किसी के बीच ग्राफ का टेन्सर उत्पाद $m$ - और $n$ -वर्टेक्स सर्कुलेंट्स अपने आप में एक सर्कुलेंट है।^[2]

रैमसे संख्या पर ज्ञात निचली सीमाओं में से कई सर्कुलेंट ग्राफ़ के उदाहरणों से आते हैं जिनमें छोटे अधिकतम क्लिक्स और छोटे अधिकतम स्वतंत्र सेट होते हैं।^[1]

एक विशिष्ट उदाहरण

गोलाकार ग्राफ $C_{n}^{s_{1},\ldots ,s_{k}}$ छलांग के साथ $s_{1},\ldots ,s_{k}$ के साथ ग्राफ के रूप में परिभाषित किया गया है $n$ नोड्स लेबल $0,1,\ldots ,n-1$ जहां प्रत्येक नोड i 2k नोड्स के निकट है $i\pm s_{1},\ldots ,i\pm s_{k}\mod n$ .

लेखाचित्र $C_{n}^{s_{1},\ldots ,s_{k}}$ अगर और केवल अगर जुड़ा हुआ है $\gcd(n,s_{1},\ldots ,s_{k})=1$ .
अगर $1\leq s_{1}<\cdots <s_{k}$ $1\leq s_{1}<\cdots <s_{k}$ निश्चित पूर्णांक हैं तो फैले हुए पेड़ों की संख्या $t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}$ $t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}$ कहाँ $a_{n}$ $a_{n}$ आदेश के पुनरावृत्ति संबंध को संतुष्ट करता है $2^{s_{k}-1}$ $2^{s_{k}-1}$ .
- विशेष रूप से, $t(C_{n}^{1,2})=nF_{n}^{2}$ कहाँ $F_{n}$ n-वें फाइबोनैचि संख्या है।

स्व पूरक परिसंचारी

एक स्व-पूरक ग्राफ एक ऐसा ग्राफ है जिसमें प्रत्येक किनारे को एक गैर-किनारे द्वारा प्रतिस्थापित किया जाता है और इसके विपरीत एक ग्राफ समरूपता ग्राफ बनाता है। उदाहरण के लिए, एक पांच-शीर्ष चक्र ग्राफ स्व-पूरक है, और एक सर्कुलेंट ग्राफ भी है। आम तौर पर प्राइम ऑर्डर का हर पाले ग्राफ एक स्व-पूरक सर्कुलेंट ग्राफ होता है।^[4] होर्स्ट सैक्स ने दिखाया कि यदि एक संख्या $n$ के पास वह गुण है जिसका प्रत्येक अभाज्य गुणनखंड $n$ के अनुरूप है 1 modulo 4, तो इसके साथ एक स्व-पूरक परिसंचारक मौजूद है $n$ शिखर। उन्होंने अनुमान लगाया कि यह शर्त भी आवश्यक है: कि कोई अन्य मूल्य नहीं $n$ स्व-पूरक परिसंचारक के अस्तित्व की अनुमति दें।^[2]^[4]विलफ्रेड द्वारा लगभग 40 साल बाद अनुमान सिद्ध किया गया था।^[2]

Ádám का अनुमान

एक सर्कुलेंट ग्राफ की सर्कुलेंट नंबरिंग को 0 से लेकर संख्याओं द्वारा ग्राफ के कोने की लेबलिंग के रूप में परिभाषित करें $n - 1$ इस तरह से कि, यदि कुछ दो शीर्षों को क्रमांकित किया गया है $x$ और $y$ सन्निकट हैं, तो प्रत्येक दो शीर्षों को क्रमांकित किया गया है $z$ और $(z - x + y) mod n$ सटे हुए हैं। समतुल्य रूप से, एक सर्कुलेंट नंबरिंग वर्टिकल की एक संख्या है जिसके लिए ग्राफ का आसन्न मैट्रिक्स एक सर्कुलेंट मैट्रिक्स है।

होने देना $a$ एक पूर्णांक हो जो अपेक्षाकृत प्रमुख हो $n$ , और जाने $b$ कोई पूर्णांक हो। फिर रैखिक कार्य जो एक संख्या लेता है $x$ को $ax + b$ एक सर्कुलेंट नंबरिंग को दूसरे सर्कुलेंट नंबरिंग में बदल देता है। एंड्रस एडम ने अनुमान लगाया कि ये रेखीय मानचित्र सर्कुलेंट संपत्ति को संरक्षित करते हुए सर्कुलेंट ग्राफ को फिर से क्रमांकित करने के एकमात्र तरीके हैं: अर्थात, यदि $G$ और $H$ आइसोमॉर्फिक सर्कुलेंट ग्राफ़ हैं, अलग-अलग नंबरिंग के साथ, फिर एक लीनियर मैप है जो नंबरिंग को बदल देता है $G$ के लिए नंबरिंग में $H$ . हालाँकि, एडम का अनुमान अब झूठा माना जाता है। रेखांकन द्वारा एक प्रति उदाहरण दिया गया है $G$ और $H$ प्रत्येक 16 शीर्षों के साथ; एक शिखर $x$ में $G$ छह पड़ोसियों से जुड़ा है $x \pm 1$ , $x \pm 2$ , और $x \pm 7$ मॉड्यूल 16, जबकि अंदर $H$ छह पड़ोसी हैं $x \pm 2$ , $x \pm 3$ , और $x \pm 5$ मोडुलो 16। ये दो रेखांकन समरूपी हैं, लेकिन उनके समरूपता को एक रेखीय मानचित्र द्वारा महसूस नहीं किया जा सकता है।^[2]

टायडा का अनुमान केवल सर्कुलेंट ग्राफ के एक विशेष वर्ग पर विचार करके एडम के अनुमान को परिष्कृत करता है, जिसमें आसन्न ग्राफ वर्टिकल के बीच के सभी अंतर वर्टिकल की संख्या के अपेक्षाकृत प्रमुख हैं। इस परिष्कृत अनुमान के अनुसार, इन विशेष सर्कुलेंट ग्राफ़ में यह गुण होना चाहिए कि उनकी सभी समरूपताएँ संख्याओं के अंतर्निहित योगात्मक समूह की समरूपता से आती हैं। $n$ . यह 2001 और 2002 में दो समूहों द्वारा सिद्ध किया गया था।^[5]^[6]

एल्गोरिथम प्रश्न

सर्कुलेंट ग्राफ़ के लिए एक बहुपद-समय मान्यता एल्गोरिथ्म है, और सर्कुलेंट ग्राफ़ के लिए आइसोमोर्फिज़्म समस्या को बहुपद समय में हल किया जा सकता है।^[7]^[8]

संदर्भ

↑ ^1.0 ^1.1 Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey 1, updated 2014.
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 Vilfred, V. (2004), "On circulant graphs", in Balakrishnan, R.; Sethuraman, G.; Wilson, Robin J. (eds.), Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001), Alpha Science, pp. 34–36.
↑ Alspach, Brian (1997), "Isomorphism and Cayley graphs on abelian groups", Graph symmetry (Montreal, PQ, 1996), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 497, Dordrecht: Kluwer Acad. Publ., pp. 1–22, MR 1468786.
↑ ^4.0 ^4.1 Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen. 9: 270–288. MR 0151953..
↑ Muzychuk, Mikhail; Klin, Mikhail; Pöschel, Reinhard (2001), "The isomorphism problem for circulant graphs via Schur ring theory", Codes and association schemes (Piscataway, NJ, 1999), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 56, Providence, Rhode Island: American Mathematical Society, pp. 241–264, MR 1816402
↑ Dobson, Edward; Morris, Joy (2002), "Toida's conjecture is true", Electronic Journal of Combinatorics, 9 (1): R35:1–R35:14, MR 1928787
↑ Muzychuk, Mikhail (2004). "A Solution of the Isomorphism Problem for Circulant Graphs". Proc. London Math. Soc. 88: 1–41. doi:10.1112/s0024611503014412. MR 2018956.
↑ Evdokimov, Sergei; Ponomarenko, Ilia (2004). "Recognition and verification of an isomorphism of circulant graphs in polynomial time". St. Petersburg Math. J. 15: 813–835. doi:10.1090/s1061-0022-04-00833-7. MR 2044629.

बाहरी संबंध

Weisstein, Eric W. "Circulant Graph". MathWorld.

[ds1-1] 1.0 ^1.1 Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey 1, updated 2014.

[v04-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 Vilfred, V. (2004), "On circulant graphs", in Balakrishnan, R.; Sethuraman, G.; Wilson, Robin J. (eds.), Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001), Alpha Science, pp. 34–36.

[3] Alspach, Brian (1997), "Isomorphism and Cayley graphs on abelian groups", Graph symmetry (Montreal, PQ, 1996), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 497, Dordrecht: Kluwer Acad. Publ., pp. 1–22, MR 1468786.

[s62-4] 4.0 ^4.1 Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen. 9: 270–288. MR 0151953..

[5] Muzychuk, Mikhail; Klin, Mikhail; Pöschel, Reinhard (2001), "The isomorphism problem for circulant graphs via Schur ring theory", Codes and association schemes (Piscataway, NJ, 1999), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 56, Providence, Rhode Island: American Mathematical Society, pp. 241–264, MR 1816402

[6] Dobson, Edward; Morris, Joy (2002), "Toida's conjecture is true", Electronic Journal of Combinatorics, 9 (1): R35:1–R35:14, MR 1928787

[muz04-7] Muzychuk, Mikhail (2004). "A Solution of the Isomorphism Problem for Circulant Graphs". Proc. London Math. Soc. 88: 1–41. doi:10.1112/s0024611503014412. MR 2018956.

[ep04-8] Evdokimov, Sergei; Ponomarenko, Ilia (2004). "Recognition and verification of an isomorphism of circulant graphs in polynomial time". St. Petersburg Math. J. 15: 813–835. doi:10.1090/s1061-0022-04-00833-7. MR 2044629.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Anonymous

Search

सर्कुलेंट ग्राफ

Namespaces

More

Page actions

Contents

समतुल्य परिभाषाएँ

उदाहरण

एक विशिष्ट उदाहरण

स्व पूरक परिसंचारी

Ádám का अनुमान

एल्गोरिथम प्रश्न

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सर्कुलेंट ग्राफ

समतुल्य परिभाषाएँ

उदाहरण

एक विशिष्ट उदाहरण

स्व पूरक परिसंचारी

Ádám का अनुमान

एल्गोरिथम प्रश्न

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories