विंडमिल ग्राफ
| 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 में शामिल होने से n पूरे ग्राफ की प्रतियां Kk एक साझा सार्वभौमिक शीर्ष पर। अर्थात्, यह इन पूर्ण रेखांकन का एक गुट-योग|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.
