거리-정규 그래프

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "거리 정규 그래프" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2009년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

자동화에 의해 정의된 그래프 패밀리
거리 변환의	→	거리 규칙의	←	매우 규칙적인.
↓
대칭(대칭 변환)	←	t-변환, t ≥ 2		꼬불꼬불한
↓
(연결된 경우) 정점 및 에지 변환	→	가장자리-변환적이고 규칙적인	→	가장자리-변환성
↓		↓		↓
정점 변환의	→	정칙의	→	(양립할 경우) 복엽의
↑
케이리 그래프	←	무궤도적		비대칭의

수학에서 거리 정규 그래프는 정규 그래프로서 어떤 두 꼭지점 v와 w의 경우, v로부터 거리 j와 w에서 거리 k에서의 정점 수는 j, k, i = d(v, w)에만 의존한다.

모든 거리 변환 그래프는 거리 규칙적이다.실제로 거리 정규 그래프는 거리 변환 그래프의 조합 일반화로서 도입되었으며, 큰 자동 형태 그룹을 가질 필요 없이 후자의 수치 정규성 특성을 가지고 있다.

교차로 배열

It turns out that a graph ${\displaystyle G}$ of diameter ${\displaystyle d}$ is distance-regular if and only if there is an array of integers ${\displaystyle \{b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d}\}}$ such that for all ${\displaystyle 1\$$leq j\leq d$ $b{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$은$($는) $v{\displaystyle }$ {\$displaystyle v}$에서 ${\displaystyle \mathrm{거리}}$ j ${\displaystyle +}$ 1에서$u$ {\$displaystyle j+1$}의 인접 항목 수를 $표시$하며$,$ c {\$displaystyle$$c_{$j}은 $j-1$에서$$$u$$$ ${\$$displaystystyleane-1$$}$의 인접 항목 수를 표시한다$$.${\displaystyle }$$G{\displaystyle }$ ${\displaystyle G}$의 거리 $j{\displaystyle }$ ${\displaystyle j}$에서 모든 꼭지점 u {\$displaystyle{\displaystyle }$ u$}$ 및 v {\$displaystyle v}$ 쌍에 대한$$$$ {\$displaystystyle v$$\}.$ 거리 정규 그래프의 특성을 나타내는 정수 배열을 교차 배열이라고 한다.

등거리-정규격

연결된 거리-정규 그래프 쌍은 동일한 교차로 배열을 가진 경우에만 동일하다.

거리 정규 그래프는 공동 거리 정규 그래프의 결합이 아닌 경우에만 연결이 끊긴다.

특성.

Suppose ${\displaystyle G}$ is a connected distance-regular graph of valency ${\displaystyle k}$ with intersection array ${\displaystyle \{b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d}\}}$. For all ${\displaystyle 0\leq j\leq d}$: let ${\displaystyle G_j}$${\displaystyle$ $G_$${j}}$은(는) $거리{\displaystyle }$ j ${\displaystyle$ $G$$}$에서 정점 쌍을 연관시켜 형성된$$ ${\displaystyle k_{}}$ j ${\$이(가) 있는$$ k ${\displaystyle j_{}}$ ${\$ 정규 그래프를 나타내며$$$,$ ${\displaystyle j_{}}$는 ${\}$의 인접 횟수를 나타낸다$$.$G{\displaystyle }$ ${\displaystyle G}$의 거리 $j{\displaystyle }$ ${\displaystyle$ j$}$에서 v ${\displaystyle$ $u}$ 및 $v{\displaystyle }$ ${\displaystyle$ v$}$의 모든 $꼭지점$ 쌍에$$ 대해 v {\$displaystyle$ u}에서 $displaystystyle$ u$}$을($으{\displaystyle }$)로$$ 표시하십시오$.$

그래프-이론적 특성

• ${\displaystyle \frac{k_{}}{}}$+ ${\displaystyle \frac{{}_{}}{{}_{}}}$ ${\displaystyle \frac{j_{}}{}}$= b ${\displaystyle \frac{j_{}}{}}$ ${\displaystyle \frac{c_{}}{}}$ ${\displaystyle \frac{{\mathrm{j}}_{}}{}}$+ 1 ${\$1}}{j+$1}}}$은(는) 0 < > ${\displaystyle 0\leq$ j$<d}$.
• ${\displaystyle b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0}$ and ${\displaystyle 1=c_{1}\leq \cdots \leq c_{d}\leq b_{0}}$.

스펙트럼 특성

• ${\displaystyle }$$k{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{2}{}}$( m${\displaystyle }$- ${\displaystyle 1}$)${\displaystyle }$(${\displaystyle m}$+ ${\displaystyle 2}$)$$G {\$displaystyle$ $k\leq {\frac {1}{1$}{1$}(m-1)(m+2)}$이(가) G ${\$$displaystyle$ $G$$}$의 고유값 m> $1${\$displaystystyle$ G$}$에 대해$$ 완전한 다중점 그래프인$$ 경우$.$
• ${\displaystyle }$$d{\displaystyle }$ G ${\displaystyle G}$이(가) 사이클 그래프 또는 전체 다중 사이트 그래프가 아닌$$ 한$,$ G ${\displaystyle G}$의 고유값 다중성 m > ${\displaystyle m>1}$에 대한$$ d ${\displaystyle \le }$ ${\displaystyle \mathrm{3m}}$- 4 ${\displaystystyle d_m-4}$
• ${\displaystyle \lambda \{}$± ${\displaystyle k\}\}}$ ${\displaystyle \lambda \in \{\pm$ k$\}}$ 만약 $if$ ${\displaystyle \lambda }}$이(가) $G{\displaystyle }$ ${\displaystyle G}$의 단순한 고유값인 경우$$$.$
• ${\displaystyle G}$ ${\displaystyle G}$에는 $d{\displaystyle }$+ 1 ${\displaystyle d+1}$개의$$ 고유값이 있다$$.

$G{\displaystyle }$ ${\displaystyle G}$이(가) 강하게 규칙적인 경우$$ $n{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle \mathrm{4m}}$- ${\displaystyle 1}$ $[\displaystyle n\leq 4m-1}$ 및$$ $k{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle \mathrm{2m}}$- 1 $[\displaystyle k\leq 2m-1$

예

거리 정규 그래프의 첫 번째 예는 다음과 같다.

• 전체 그래프.
• 사이클 그래프.
• 이상한 그래프.
• 무어 그래프.
• 폴리곤 근처에 있는 일반 폴리곤의 공선도 그래프.
• 웰스 그래프와 실베스터 그래프.
• 직경 $2{\displaystyle \mathrm{}}$ ${\displaystyle 2}$의 매우 정규적인 그래프$.$

거리-정규 그래프

주어진 k> $[\displaystyle k >2}$에 대한 명확한 연결 거리 정규 그래프만 매우 많다^[1]

마찬가지로, 주어진 고유값 m> ${\displaystyle m>2}($전체 다중 사이트 그래프는 제외)을 가진 개별적인 연결 거리 정규 그래프만 있다.^[2]

세제곱 거리 정규 그래프

세제곱 거리 정규 그래프는 완전히 분류되었다.

The 13 distinct cubic distance-regular graphs are K₄ (or Tetrahedral graph), K_3,3, the Petersen graph, the Cubical graph, the Heawood graph, the Pappus graph, the Coxeter graph, the Tutte–Coxeter graph, the Dodecahedral graph, the Desargues graph, Tutte 12-cage, the Biggs–Smith graph, and the Foster graph.

참조

추가 읽기

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