बुल ग्राफ

Bull graph
The bull graph
Vertices	5
Edges	5
Radius	2
Diameter	3
Girth	3
Automorphisms	2 (Z/2Z)
Chromatic number	3
Chromatic index	3
Properties	Planar Unit distance
Table of graphs and parameters

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

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

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

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

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

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

रंगीन बहुपद के साथ तीन ग्राफ़ बराबर हैं $(x-2)(x-1)^{3}x$.

बुल ग्राफ का रंगीन बहुपद है $(x-2)(x-1)^{3}x$. दो अन्य ग्राफ़ गुणात्मक रूप से बुल ग्राफ़ के समतुल्य हैं।

इसका अभिलक्षणिक बहुपद है $-x(x^{2}-x-3)(x^{2}+x-1)$.

इसका टुट्टे बहुपद है $x^{4}+x^{3}+x^{2}y$.