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

ऑर्डर 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$ के निकट है।

ग्राफ $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 मॉड्यूल 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