विंडमिल ग्राफ
| Windmill graph | |
|---|---|
.svg) The Windmill graph Wd(5,4). | |
| Vertices | n(k – 1) + 1 |
| Edges | nk(k − 1)/2 |
| Radius | 1 |
| Diameter | 2 |
| Girth | 3 if k > 2 |
| Chromatic number | k |
| Chromatic index | n(k – 1) |
| Notation | Wd(k,n) |
| Table of graphs and parameters | |
ग्राफ सिद्धांत के गणित क्षेत्र में विंडमिल ग्राफ Wd(k,n) एक अप्रत्यक्ष ग्राफ है। जिसे k ≥ 2 और n ≥ 2 के लिए एक वितरित यूनिवर्सल वर्टेक्स पर पूर्ण ग्राफ Kk की n प्रतियों में सम्मिलित करके बनाया गया है अर्थात् यह इन पूर्ण ग्राफ़ों का 1-क्लिक-योग है।[1]
गुण
यह है n(k – 1) + 1 शिखर और nk(k − 1)/2 किनारों,[2] परिधि 3 (यदि k > 2), त्रिज्या 1 और व्यास 2। इसका के-वर्टेक्स-कनेक्टेड ग्राफ 1 है क्योंकि इसका केंद्रीय शीर्ष एक आर्टिक्यूलेशन पॉइंट है; हालाँकि, पूर्ण रेखांकन की तरह जिससे यह बनता है, यह है (k – 1)-एज-कनेक्टेड। यह तुच्छ रूप से सही ग्राफ और एक ब्लॉक ग्राफ है।
विशेष मामले
निर्माण द्वारा, पवनचक्की ग्राफ Wd(3,n) दोस्ती का ग्राफ है Fn, पवनचक्की ग्राफ Wd(2,n) तारा है (ग्राफ सिद्धांत) Sn और पवनचक्की ग्राफ Wd(3,2) तितली ग्राफ है।
लेबलिंग और रंग
पवनचक्की ग्राफ में रंगीन संख्या होती है k और रंगीन सूचकांक n(k – 1). इसका रंगीन बहुपद पूरे ग्राफ के रंगीन बहुपद से निकाला जा सकता है और इसके बराबर है
पवनचक्की ग्राफ Wd(k,n) अगर ग्रेसफुल लेबलिंग साबित नहीं हुई है k > 5.[3] 1979 में, बरमोंड ने अनुमान लगाया है Wd(4,n) सबके लिए कृपालु है n ≥ 4.[4] पूर्ण अंतर परिवारों के साथ एक तुल्यता के माध्यम से, यह साबित हो गया है n ≤ 1000. [5] बरमोंड, एंटोन कोटज़िग और टर्जन ने यह साबित कर दिया Wd(k,n) कृपालु नहीं है जब k = 4 और n = 2 या n = 3, और जब k = 5 और n = 2.[6] पवनचक्की Wd(3,n) कृपालु है अगर और केवल अगर n ≡ 0 (mod 4) या n ≡ 1 (mod 4).[7]
गैलरी
संदर्भ
- ↑ Gallian, J. A. (3 January 2007). "ग्राफ लेबलिंग का एक गतिशील सर्वेक्षण" (PDF). Electronic Journal of Combinatorics. DS6: 1–58. MR 1668059.
- ↑ Weisstein, Eric W. "Windmill Graph". MathWorld.
- ↑ Koh, K. M.; Rogers, D. G.; Teo, H. K.; Yap, K. Y. (1980). "Graceful graphs: some further results and problems". Congressus Numerantium. 29: 559–571. MR 0608456.
- ↑ Bermond, J.-C. (1979). "Graceful graphs, radio antennae and French windmills". In Wilson, Robin J. (ed.). Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978). Research notes in mathematics. Vol. 34. Pitman. pp. 18–37. ISBN 978-0273084358. MR 0587620. OCLC 757210583.
- ↑ Ge, G.; Miao, Y.; Sun, X. (2010). "परफेक्ट डिफरेंस फैमिली, परफेक्ट डिफरेंस मैट्रिसेस और संबंधित कॉम्बिनेटरियल स्ट्रक्चर". Journal of Combinatorial Designs. 18 (6): 415–449. doi:10.1002/jcd.20259. MR 2743134.
- ↑ Bermond, J.-C.; Kotzig, A.; Turgeon, J. (1978). "On a combinatorial problem of antennas in radioastronomy". In Hajnal, A.; Sos, Vera T. (eds.). Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I. Colloquia mathematica Societatis János Bolyai. Vol. 18. North-Holland. pp. 135–149. ISBN 978-0-444-85095-9. MR 0519261.
- ↑ Bermond, J.-C.; Brouwer, A. E.; Germa, A. (1978). "Systèmes de triplets et différences associées". Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Colloques internationaux du Centre National de la Recherche Scientifique. Vol. 260. Éditions du Centre national de la recherche scientifique. pp. 35–38. ISBN 978-2-222-02070-7. MR 0539936.
