- Source: Distance-regular graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and the distance between v and w.
Some authors exclude the complete graphs and disconnected graphs from this definition.
Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group.
Intersection arrays
The intersection array of a distance-regular graph is the array
(
b
0
,
b
1
,
…
,
b
d
−
1
;
c
1
,
…
,
c
d
)
{\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}
in which
d
{\displaystyle d}
is the diameter of the graph and for each
1
≤
j
≤
d
{\displaystyle 1\leq j\leq d}
,
b
j
{\displaystyle b_{j}}
gives the number of neighbours of
u
{\displaystyle u}
at distance
j
+
1
{\displaystyle j+1}
from
v
{\displaystyle v}
and
c
j
{\displaystyle c_{j}}
gives the number of neighbours of
u
{\displaystyle u}
at distance
j
−
1
{\displaystyle j-1}
from
v
{\displaystyle v}
for any pair of vertices
u
{\displaystyle u}
and
v
{\displaystyle v}
at distance
j
{\displaystyle j}
. There is also the number
a
j
{\displaystyle a_{j}}
that gives the number of neighbours of
u
{\displaystyle u}
at distance
j
{\displaystyle j}
from
v
{\displaystyle v}
. The numbers
a
j
,
b
j
,
c
j
{\displaystyle a_{j},b_{j},c_{j}}
are called the intersection numbers of the graph. They satisfy the equation
a
j
+
b
j
+
c
j
=
k
,
{\displaystyle a_{j}+b_{j}+c_{j}=k,}
where
k
=
b
0
{\displaystyle k=b_{0}}
is the valency, i.e., the number of neighbours, of any vertex.
It turns out that a graph
G
{\displaystyle G}
of diameter
d
{\displaystyle d}
is distance regular if and only if it has an intersection array in the preceding sense.
Cospectral and disconnected distance-regular graphs
A pair of connected distance-regular graphs are cospectral if their adjacency matrices have the same spectrum. This is equivalent to their having the same intersection array.
A distance-regular graph is disconnected if and only if it is a disjoint union of cospectral distance-regular graphs.
Properties
Suppose
G
{\displaystyle G}
is a connected distance-regular graph of valency
k
{\displaystyle k}
with intersection array
(
b
0
,
b
1
,
…
,
b
d
−
1
;
c
1
,
…
,
c
d
)
{\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}
. For each
0
≤
j
≤
d
,
{\displaystyle 0\leq j\leq d,}
let
k
j
{\displaystyle k_{j}}
denote the number of vertices at distance
k
{\displaystyle k}
from any given vertex and let
G
j
{\displaystyle G_{j}}
denote the
k
j
{\displaystyle k_{j}}
-regular graph with adjacency matrix
A
j
{\displaystyle A_{j}}
formed by relating pairs of vertices on
G
{\displaystyle G}
at distance
j
{\displaystyle j}
.
= Graph-theoretic properties
=k
j
+
1
k
j
=
b
j
c
j
+
1
{\displaystyle {\frac {k_{j+1}}{k_{j}}}={\frac {b_{j}}{c_{j+1}}}}
for all
0
≤
j
<
d
{\displaystyle 0\leq j
.
b
0
>
b
1
≥
⋯
≥
b
d
−
1
>
0
{\displaystyle b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0}
and
1
=
c
1
≤
⋯
≤
c
d
≤
b
0
{\displaystyle 1=c_{1}\leq \cdots \leq c_{d}\leq b_{0}}
.
= Spectral properties
=G
{\displaystyle G}
has
d
+
1
{\displaystyle d+1}
distinct eigenvalues.
The only simple eigenvalue of
G
{\displaystyle G}
is
k
,
{\displaystyle k,}
or both
k
{\displaystyle k}
and
−
k
{\displaystyle -k}
if
G
{\displaystyle G}
is bipartite.
k
≤
1
2
(
m
−
1
)
(
m
+
2
)
{\displaystyle k\leq {\frac {1}{2}}(m-1)(m+2)}
for any eigenvalue multiplicity
m
>
1
{\displaystyle m>1}
of
G
,
{\displaystyle G,}
unless
G
{\displaystyle G}
is a complete multipartite graph.
d
≤
3
m
−
4
{\displaystyle d\leq 3m-4}
for any eigenvalue multiplicity
m
>
1
{\displaystyle m>1}
of
G
,
{\displaystyle G,}
unless
G
{\displaystyle G}
is a cycle graph or a complete multipartite graph.
If
G
{\displaystyle G}
is strongly regular, then
n
≤
4
m
−
1
{\displaystyle n\leq 4m-1}
and
k
≤
2
m
−
1
{\displaystyle k\leq 2m-1}
.
Examples
Some first examples of distance-regular graphs include:
The complete graphs.
The cycle graphs.
The odd graphs.
The Moore graphs.
The collinearity graph of a regular near polygon.
The Wells graph and the Sylvester graph.
Strongly regular graphs of diameter
2
{\displaystyle 2}
.
Classification of distance-regular graphs
There are only finitely many distinct connected distance-regular graphs of any given valency
k
>
2
{\displaystyle k>2}
.
Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity
m
>
2
{\displaystyle m>2}
(with the exception of the complete multipartite graphs).
= Cubic distance-regular graphs
=The cubic distance-regular graphs have been completely classified.
The 13 distinct cubic distance-regular graphs are K4 (or Tetrahedral graph), K3,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.
References
Further reading
Godsil, C. D. (1993). Algebraic Combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall. ISBN 978-0-412-04131-0. MR 1220704.
Kata Kunci Pencarian:
- Limas persegi
- Daftar masalah matematika yang belum terpecahkan
- Distance-regular graph
- Regular graph
- Strongly regular graph
- Symmetric graph
- Distance-transitive graph
- Heawood graph
- Petersen graph
- Desargues graph
- Cycle graph
- Unit distance graph
