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

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)$ किसी भी आइजन मान की बहुलता के लिए $m>1$ का मान $G$ द्वारा प्रकट होता हैं, जब तक $G$ पूर्ण बहुपक्षीय ग्राफ है।
• $d\leq 3m-4$ किसी भी आइजन मान की बहुलता के लिए $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$ हैं। इसी प्रकार किसी भी दिए गए आइजन मान बहुलता के साथ केवल बहुत ही अलग-अलग जुड़े दूरी-नियमित ग्राफ़ $m>2$ हैं। (पूर्ण बहुपक्षीय रेखांकन के अपवाद के साथ होता हैं)।

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

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

13 विशिष्ट क्यूबिक दूरी-नियमित ग्राफ़ पूर्ण ग्राफ़ हैं | K₄(या टेट्राहेड्रल ग्राफ), पूर्ण द्विदलीय ग्राफ या K_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.