विंडमिल ग्राफ
| 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 किनारों, परिधि 3 (यदि k > 2), त्रिज्या 1 और व्यास 2 है।[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]
बरमोंड, एंटोन कोटज़िग और टर्जन ने सिद्ध किया कि जब k = 4 और n = 2 या n = 3 और जब k = 5 और n = 2 होता है। तो Wd(k,n) सुंदर नहीं होता है।[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.
