दूरी-नियमित ग्राफ

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	[[symmetric graph|t-transitive, t ≥ 2]]		skew-symmetric
↓
(if connected) vertex- and edge-transitive	→	edge-transitive and regular	→	edge-transitive
↓		↓		↓
vertex-transitive	→	regular	→	(if bipartite) biregular
↑
Cayley graph	←	zero-symmetric		asymmetric

ग्राफ़ सिद्धांत के गणितीय क्षेत्र में, एक दूरी-नियमित ग्राफ़ एक नियमित ग्राफ़ है जैसे कि किसी भी दो वर्टेक्स (ग्राफ़ सिद्धांत) के लिए v और w, दूरी पर शीर्षों की संख्या (ग्राफ़ सिद्धांत) j से v और दूरी पर k से w पर ही निर्भर करता है j, k, और बीच की दूरी v और w.

कुछ लेखक इस परिभाषा से पूर्ण रेखांकन और डिस्कनेक्ट किए गए रेखांकन को बाहर करते हैं।

प्रत्येक दूरी-सकर्मक ग्राफ दूरी-नियमित होता है। वास्तव में, दूरी-नियमित रेखांकन को दूरी-सकर्मक रेखांकन के संयोजी सामान्यीकरण के रूप में पेश किया गया था, जिसमें आवश्यक रूप से बड़े ग्राफ ऑटोमोर्फिज्म के बिना बाद के संख्यात्मक नियमितता गुण होते हैं।

प्रतिच्छेदन सरणियाँ

यह पता चला है कि एक ग्राफ $G$ व्यास का $d$ दूरी-नियमित है अगर और केवल अगर पूर्णांकों की एक सरणी है $\{b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d}\}$ ऐसा कि सभी के लिए $1\leq j\leq d$, $b_{j}$ के पड़ोसियों की संख्या देता है $u$ दूरी पर $j+1$ से $v$ और $c_{j}$ के पड़ोसियों की संख्या देता है $u$ दूरी पर $j-1$ से $v$ किसी भी जोड़ी के शिखर के लिए $u$ और $v$ दूरी पर $j$ पर $G$. दूरी-नियमित ग्राफ़ की विशेषता वाले पूर्णांकों की सरणी को इसके प्रतिच्छेदन सरणी के रूप में जाना जाता है।

कोस्पेक्ट्रल दूरी-नियमित रेखांकन

कनेक्टेड डिस्टेंस-रेगुलर ग्राफ़ की एक जोड़ी स्पेक्ट्रल ग्राफ सिद्धांत है अगर और केवल अगर उनके पास एक ही इंटरसेक्शन एरे है।

एक दूरी-नियमित ग्राफ़ डिस्कनेक्ट हो जाता है यदि और केवल यदि यह कोस्पेक्ट्रल दूरी-नियमित ग्राफ़ का ग्राफ़ संघ है।

गुण

कल्पना करना $G$ डिग्री का एक जुड़ा हुआ दूरी-नियमित ग्राफ है (ग्राफ सिद्धांत) $k$ चौराहे सरणी के साथ $\{b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d}\}$. सभी के लिए $0\leq j\leq d$: होने देना $G_{j}$ निरूपित करें $k_{j}$आसन्न मैट्रिक्स के साथ नियमित ग्राफ $A_{j}$ पर शीर्षों के जोड़े को जोड़कर बनाया गया $G$ दूरी पर $j$, और जाने $a_{j}$ के पड़ोसियों की संख्या को निरूपित करें $u$ दूरी पर $j$ से $v$ किसी भी जोड़ी के शिखर के लिए $u$ और $v$ दूरी पर $j$ पर $G$.

ग्राफ-सैद्धांतिक गुण

• ${\frac {k_{j+1}}{k_{j}}}={\frac {b_{j}}{c_{j+1}}}$ सभी के लिए $0\leq j<d$.
• $b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0$ और $1=c_{1}\leq \cdots \leq c_{d}\leq b_{0}$.

स्पेक्ट्रल गुण

• $k\leq {\frac {1}{2}}(m-1)(m+2)$ किसी भी eigenvalue बहुलता के लिए $m>1$ का $G$, जब तक $G$ एक पूर्ण बहुपक्षीय ग्राफ है।
• $d\leq 3m-4$ किसी भी eigenvalue बहुलता के लिए $m>1$ का $G$, जब तक $G$ एक चक्र ग्राफ या एक पूर्ण बहुपक्षीय ग्राफ है।
• $\lambda \in \{\pm k\}$ अगर $\lambda$ का एक साधारण आइगेनवैल्यू है $G$.
• $G$ है $d+1$ अलग आइगेनवैल्यू।

अगर $G$ मजबूत नियमित ग्राफ है, फिर $n\leq 4m-1$ और $k\leq 2m-1$.

उदाहरण

डिग्री 7 क्लेन ग्राफ और संबंधित मानचित्र जीनस 3 की एक ओरिएंटेबल सतह में एम्बेडेड है। यह ग्राफ इंटरसेक्शन सरणी {7,4,1;1,2,7} और ऑटोमोर्फिज्म समूह पीजीएल (2,7) के साथ नियमित रूप से दूरी है।

दूरी-नियमित रेखांकन के कुछ पहले उदाहरणों में शामिल हैं:

• पूरा रेखांकन।
• चक्र रेखांकन।
• विषम रेखांकन।
• मूर रेखांकन।
• नियर पॉलीगॉन#रेगुलर नियर पॉलीगॉन का कोलीनियरिटी ग्राफ़।
• वेल्स ग्राफ और सिल्वेस्टर ग्राफ।
• व्यास के मजबूत नियमित रेखांकन $2$.

दूरी-नियमित रेखांकन का वर्गीकरण

किसी भी संयोजकता के केवल सूक्ष्म रूप से कई अलग-अलग जुड़े हुए दूरी-नियमित ग्राफ़ हैं $k>2$. इसी तरह, किसी भी दिए गए eigenvalue बहुलता के साथ केवल बहुत ही अलग-अलग जुड़े दूरी-नियमित ग्राफ़ हैं $m>2$ (पूर्ण बहुपक्षीय रेखांकन के अपवाद के साथ)।

घन दूरी-नियमित रेखांकन

क्यूबिक ग्राफ़ दूरी-नियमित ग्राफ़ को पूरी तरह से वर्गीकृत किया गया है।

13 विशिष्ट क्यूबिक दूरी-नियमित ग्राफ़ पूर्ण ग्राफ़ हैं | के₄(या टेट्राहेड्रल ग्राफ), पूर्ण द्विदलीय ग्राफ | के_3,3, पीटरसन ग्राफ, क्यूबिकल ग्राफ, हीवुड ग्राफ , पप्पू ग्राफ, कॉक्सेटर ग्राफ, टुट्टे-कॉक्सेटर ग्राफ, डोडेकाहेड्रल ग्राफ, Desargues ग्राफ, सभी 12-पिंजरे, बिग्स-स्मिथ ग्राफ और फोस्टर ग्राफ .

अग्रिम पठन

• Godsil, C. D. (1993). Algebraic Combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall. ISBN 978-0-412-04131-0. MR 1220704.