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

क्रम 13 का पाले ग्राफ सर्कुलेंट ग्राफ का उदाहरण है।

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

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

सर्कुलेंट ग्राफ़ का वर्णन विभिन्न प्रकारों द्वारा किया जा सकता है-^[2]

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

उदाहरण

प्रत्येक चक्र ग्राफ सर्कुलेंट ग्राफ होते है। क्राउन ग्राफ में 2 मॉडुलो 4 शीर्ष होते हैं।

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

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

यदि दो संख्याएँ $m$ और $n$ सह-अभाज्य संख्याएँ हैं, तो $m \times n$ रूक का ग्राफ़ (ग्राफ़ जिसमें $m \times n$ शतरंजबोर्ड के प्रत्येक वर्ग के लिए शीर्ष है और प्रत्येक दो वर्गों के लिए कोर है जो शतरंज के रूक के मध्य समान चलन में आगे बढ़ सकता है) सर्कुलेंट ग्राफ है। ऐसा इसलिए है क्योंकि इसकी समरूपता में उपसमूह के रूप में चक्रीय समूह C_mn C_m×C_n सम्मिलित है। सामान्यतः, इस स्थिति में, $m$ - और $n$ -शीर्ष के मध्य ग्राफ का टेन्सर गुणनफल सर्कुलेंट होता है।^[2]

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

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

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

यदि $\gcd(n,s_{1},\ldots ,s_{k})=1$ है, तो ग्राफ $C_{n}^{s_{1},\ldots ,s_{k}}$ युग्मित है।
यदि $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 मॉड्यूल 4 के सर्वांगसम है, तो $n$ शीर्षों के साथ स्व-पूरक परिसंचारक उपस्थित होता है। उनका आकलन है, कि $n$ का मान स्व-पूरक परिसंचारक के अस्तित्व की अनुमति प्रदान नहीं करता है।^[2]^[4]विलफ्रेड द्वारा प्रायः 40 वर्ष पश्चात यह आकलन सिद्ध किया गया था।^[2]

एडम का अनुमान

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

मान लीजिए $a$ पूर्णांक है जो $n$ से सह-अभाज्य है, और $b$ कोई पूर्णांक है। तब, रैखिक फलन जो संख्या $x$ को $ax + b$ में ले जाता है, जो सर्कुलेंट नंबरिंग को अन्य सर्कुलेंट नंबरिंग में परिवर्तित कर देता है। एंड्रस एडम ने अनुमान लगाया कि ये रैखिक मानचित्र सर्कुलेंट गुण को संरक्षित करते हुए सर्कुलेंट ग्राफ को पुनः क्रमांकित करने का एकमात्र प्रकार है। अर्थात, यदि $G$ और $H$ भिन्न-भिन्न नंबरिंग के साथ आइसोमॉर्फिक सर्कुलेंट ग्राफ़ हैं, तो रैखिक मानचित्र $G$ की नंबरिंग को $H$ के लिए परिवर्तित कर देता है। चूँकि, एडम के अनुमान को वर्तमान में असत्य माना जाता है। ग्राफ $G$ और $H$ प्रत्येक 16 शीर्षों के साथ प्रति उदाहरण दिया गया है, जिसमें $G$ में शीर्ष $x$ छह प्रतिवेशियों $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

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

उदाहरण

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

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

एडम का अनुमान

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

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

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

उदाहरण

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

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

एडम का अनुमान

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

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories