बुल ग्राफ

From Vigyanwiki
बुल ग्राफ
Bull graph.circo.svg
बुल ग्राफ
Vertices5
Edges5
Radius2
Diameter3
Girth3
Automorphisms2 (Z/2Z)
Chromatic number3
Chromatic index3
Propertiesतलीय
इकाई दूरी
Table of graphs and parameters

ग्राफ़ सिद्धांत के गणितीय क्षेत्र में, बुल ग्राफ़ 5 शीर्षों और 5 किनारों वाला समतलीय प्रकार का अप्रत्यक्ष ग्राफ है, जिसे दो असंयुक्त लटकन किनारों वाले त्रिकोण के रूप में दर्शाया जाता है।[1]

इस ग्राफ़ में वर्णिक संख्या 3, वर्णिक सूचकांक 3, त्रिज्या 2, व्यास 3 और परिधि (ग्राफ सिद्धांत) 3 होते है। यह ग्राफ़ स्व-पूरक ग्राफ, ब्लॉक ग्राफ, विभाजित ग्राफ, अंतराल ग्राफ और पंजा-मुक्त ग्राफ भी है। बुल ग्राफ़ 1- के-वर्टेक्स-कनेक्टेड ग्राफ़ और 1- के-एज-कनेक्टेड ग्राफ़ के प्रकार का भी होता है।

बुल-मुक्त ग्राफ़

यदि ग्राफ में प्रेरित सबग्राफ के रूप में कोई बुल नहीं है तो ग्राफ बुल-मुक्त होता है। त्रिकोण-मुक्त ग्राफ़, बु बुल-मुक्त ग्राफ होते हैं, क्योंकि प्रत्येक बुल में एक त्रिकोण होता है। बुल-मुक्त ग्राफ के लिए मज़बूत पूर्ण ग्राफ के सिद्धांत का प्रमाण आम ग्राफ के लिए इसके प्रमाण के पहले ही किया गया था,[2] और बुल-मुक्त पूर्ण ग्राफ के लिए एक बहुमुखी समय मान्यता ग्राफ पहचान के लिए भी ज्ञात है।[3]

मारिया चुडनोव्स्की और शमूएल सफरा ने बुल- मुक्त ग्राफ़ का अधिक सामान्यतः अध्ययन किया है, जिससे पता चलता है कि ऐसे किसी भी ग्राफ़ में या तो बड़ा समूह (ग्राफ़ सिद्धांत) या बड़ा स्वतंत्र समुच्चय (ग्राफ़ सिद्धांत) होना चाहिए (अर्थात, एर्दो-हजनल अनुमान बुल ग्राफ के लिए मान्य है),[4] और इन ग्राफों के लिए एक सामान्य संरचना सिद्धांत विकसित किया है।[5][6][7]

वर्णिक और चारित्रिक बहुपद

रंगीन बहुपद के साथ तीन ग्राफ़ बराबर हैं .

बुल ग्राफ का रंगीय बहुपद विकल्प निम्नलिखित है:

इसके अलावा और दो ग्राफ भी बुल ग्राफ के रंगीय समरूप हैं।

इसका लक्षण बहुपद निम्नलिखित है:

इसका सभी बहुपद निम्नलिखित है:

संदर्भ

  1. Weisstein, Eric W. "Bull Graph". MathWorld.
  2. Chvátal, V.; Sbihi, N. (1987), "Bull-free Berge graphs are perfect", Graphs and Combinatorics, 3 (1): 127–139, doi:10.1007/BF01788536, S2CID 44570627.
  3. Reed, B.; Sbihi, N. (1995), "Recognizing bull-free perfect graphs", Graphs and Combinatorics, 11 (2): 171–178, doi:10.1007/BF01929485, S2CID 206808701.
  4. Chudnovsky, M.; Safra, S. (2008), "The Erdős–Hajnal conjecture for bull-free graphs", Journal of Combinatorial Theory, Series B, 98 (6): 1301–1310, doi:10.1016/j.jctb.2008.02.005.
  5. Chudnovsky, M. (2008), The structure of bull-free graphs. I. Three-edge paths with centers and anticenters (PDF).
  6. Chudnovsky, M. (2008), The structure of bull-free graphs. II. Elementary trigraphs (PDF).
  7. Chudnovsky, M. (2008), The structure of bull-free graphs. III. Global structure (PDF).