ग्रेसफुल लेबलिंग

From Vigyanwiki
Revision as of 16:20, 18 April 2023 by alpha>Indicwiki (Created page with "{{short description|Type of graph vertex labeling}} Image:Graceful labeling.svg|thumb|एक सुंदर लेबलिंग। वर्टेक्स (ग्रा...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
एक सुंदर लेबलिंग। वर्टेक्स (ग्राफ़ थ्योरी) लेबल काले रंग में हैं, किनारे वाले लेबल लाल रंग में हैं।

ग्राफ सिद्धांत में, एक ग्राफ (असतत गणित) का एक सुंदर लेबलिंग m किनारे इसके वर्टेक्स (ग्राफ़ सिद्धांत) का एक ग्राफ लेबलिंग है जिसमें 0 से लेकर पूर्णांकों के कुछ सबसेट हैं m समावेशी, जैसे कि कोई भी दो कोने एक लेबल साझा नहीं करते हैं, और प्रत्येक किनारे को उसके समापन बिंदुओं के बीच पूर्ण अंतर से विशिष्ट रूप से पहचाना जाता है, जैसे कि यह परिमाण 1 और के बीच होता है m सहित।[1] एक ग्राफ़ जो एक ग्रेसफुल लेबलिंग को स्वीकार करता है, ग्रेसफुल ग्राफ़ कहलाता है।

ग्रेसफुल लेबलिंग का नाम सोलोमन डब्ल्यू गोलोम्ब के कारण है; इस प्रकार की लेबलिंग को मूल रूप से अलेक्जेंडर रोजा द्वारा 1967 में ग्राफ लेबलिंग पर पेपर में β-लेबलिंग नाम दिया गया था।[2] ग्राफ़ थ्योरी में एक प्रमुख अनुमान सुंदर वृक्ष अनुमान या रिंगेल-कोटज़िग अनुमान है, जिसका नाम गेरहार्ड रिंगेल और एंटोन कोटज़िग के नाम पर रखा गया है, और कभी-कभी संक्षिप्त रूप से जीटीसी।[3] यह परिकल्पना करता है कि सभी पेड़ (ग्राफ) सुंदर हैं। यह अभी भी एक खुला अनुमान है, हालांकि रिंगेल के अनुमान के रूप में जाना जाने वाला एक संबंधित लेकिन कमजोर अनुमान 2020 में आंशिक रूप से सिद्ध हुआ था।[4][5][6] 

कोटज़िग ने एक बार अनुमान को एक बीमारी साबित करने के प्रयास को कहा था।[7]

ग्रेसफुल लेबलिंग का एक और कमजोर संस्करण नियर-ग्रेसफुल लेबलिंग है, जिसमें पूर्णांकों के कुछ सबसेट का उपयोग करके कोने को लेबल किया जा सकता है [0, m + 1] जैसे कि कोई भी दो कोने एक लेबल को साझा नहीं करते हैं, और प्रत्येक किनारे को इसके समापन बिंदुओं के बीच पूर्ण अंतर से विशिष्ट रूप से पहचाना जाता है (यह परिमाण निहित है [1, m + 1]).

ग्राफ सिद्धांत में एक और अनुमान है रोजा का अनुमान, जिसका नाम अलेक्जेंडर रोजा के नाम पर रखा गया है, जो कहता है कि सभी कैक्टस ग्राफ # त्रिकोणीय कैक्टस सुंदर या लगभग-सुंदर हैं।[8] 0 से किनारों के साथ एक सुंदर ग्राफ m से कम नहीं होने का अनुमान है शिखर, विरल शासक परिणामों के कारण। यह अनुमान 213 या उससे कम किनारों वाले सभी ग्राफ़ के लिए सत्यापित किया गया है।

27 किनारों और 9 शीर्षों वाला एक सुंदर ग्राफ़

चयनित परिणाम

  • अपने मूल पेपर में, रोजा ने साबित किया कि किनारों की संख्या m ≡ 1 (mod 4) या m ≡ 2 (mod 4) के साथ एक Eulerian ग्राफ सुंदर नहीं हो सकता।[2]* साथ ही अपने मूल पत्र में, रोजा ने सिद्ध किया कि चक्र सीnग्रेसफुल है अगर और केवल अगर n ≡ 0 (mod 4) या n ≡ 3 (mod 4)।
  • सभी पथ रेखांकन और कैटरपिलर रेखांकन सुंदर हैं।
  • बिल्कुल मिलान वाले सभी लॉबस्टर ग्राफ़ सुंदर हैं।[9]
  • अधिकतम 27 शीर्षों वाले सभी पेड़ सुंदर होते हैं; यह परिणाम एल्ड्रेड और ब्रेंडन मैके (गणितज्ञ) द्वारा 1998 में एक कंप्यूटर प्रोग्राम का उपयोग करके दिखाया गया था।[10][11] इसे माइकल हॉर्टन के ऑनर्स थीसिस में अधिकतम 29 शीर्षों वाले वृक्षों तक विस्तारित किया गया था।[12] 2010 में वेंजी फैंग के नेतृत्व में एक वितरित कंप्यूटिंग परियोजना, ग्रेसफुल ट्री वेरिफिकेशन प्रोजेक्ट द्वारा 35 वर्टीकल वाले पेड़ों तक इस परिणाम का एक और विस्तार का दावा किया गया था।[13]
  • सभी पहिया ग्राफ ़, वेब ग्राफ़, पतवार का ग्राफ ़, गियर ग्राफ़ और ग्रिड ग्राफ़ # स्क्वायर ग्रिड ग्राफ़ सुंदर हैं।[10]* सभी एन-डायमेंशनल अतिविम ्स ग्रेसफुल हैं।[14]
  • चार या उससे कम शीर्षों वाले सभी साधारण ग्राफ़ सुंदर हैं। पांच कोने वाले केवल गैर-सुशोभित सरल ग्राफ 5-चक्र ग्राफ (पंचकोण) हैं; पूरा ग्राफ#उदाहरण|पूरा ग्राफ K5; और तितली ग्राफ।[15]


यह भी देखें

संदर्भ

  1. ↑ Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. PostScript
  2. ↑ 2.0 2.1 Rosa, A. (1967), "On certain valuations of the vertices of a graph", Theory of Graphs (Internat. Sympos., Rome, 1966), New York: Gordon and Breach, pp. 349–355, MR 0223271.
  3. ↑ Wang, Tao-Ming; Yang, Cheng-Chang; Hsu, Lih-Hsing; Cheng, Eddie (2015), "Infinitely many equivalent versions of the graceful tree conjecture", Applicable Analysis and Discrete Mathematics, 9 (1): 1–12, doi:10.2298/AADM141009017W, MR 3362693
  4. ↑ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2020). "रिंगेल के अनुमान का प्रमाण" (in English). arXiv:2001.02665 [math.CO].
  5. ↑ Huang, C.; Kotzig, A.; Rosa, A. (1982), "Further results on tree labellings", Utilitas Mathematica, 21: 31–48, MR 0668845.
  6. ↑ Hartnett, Kevin. "रेनबो प्रूफ से पता चलता है कि ग्राफ़ में एकसमान भाग होते हैं". Quanta Magazine (in English). Retrieved 2020-02-29.
  7. ↑ Huang, C.; Kotzig, A.; Rosa, A. (1982), "Further results on tree labellings", Utilitas Mathematica, 21: 31–48, MR 0668845.
  8. ↑ Rosa, A. (1988), "Cyclic Steiner Triple Systems and Labelings of Triangular Cacti", Scientia, 1: 87–95.
  9. ↑ Morgan, David (2008), "All lobsters with perfect matchings are graceful", Bulletin of the Institute of Combinatorics and Its Applications, 53: 82–85, hdl:10402/era.26923.
  10. ↑ 10.0 10.1 Gallian, Joseph A. (1998), "A dynamic survey of graph labeling", Electronic Journal of Combinatorics, 5: Dynamic Survey 6, 43 pp. (389 pp. in 18th ed.) (electronic), MR 1668059.
  11. ↑ Aldred, R. E. L.; McKay, Brendan D. (1998), "Graceful and harmonious labellings of trees", Bulletin of the Institute of Combinatorics and Its Applications, 23: 69–72, MR 1621760.
  12. ↑ Horton, Michael P. (2003), Graceful Trees: Statistics and Algorithms.
  13. ↑ Fang, Wenjie (2010), A Computational Approach to the Graceful Tree Conjecture, arXiv:1003.3045, Bibcode:2010arXiv1003.3045F. See also Graceful Tree Verification Project
  14. ↑ Kotzig, Anton (1981), "Decompositions of complete graphs into isomorphic cubes", Journal of Combinatorial Theory, Series B, 31 (3): 292–296, doi:10.1016/0095-8956(81)90031-9, MR 0638285.
  15. ↑ Weisstein, Eric W. "Graceful graph". MathWorld.


बाहरी संबंध


अग्रिम पठन

  • (K. Eshghi) Introduction to Graceful Graphs, Sharif University of Technology, 2002.
  • (U. N. Deshmukh and Vasanti N. Bhat-Nayak), New families of graceful banana trees – Proceedings Mathematical Sciences, 1996 – Springer
  • (M. Haviar, M. Ivaska), Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, Volume 34, 2015.
  • (Ping Zhang), A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, 2016 – Springer
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ग्रेसफुल_लेबलिंग&oldid=145666’