To find graphs for which the diameter equals one less than the

number of distinct eigenvalues.

Apoorva Vaidya (210003014)
February 25, 2025

Defining the terms and objective

• Diameter (d): The longest shortest path between any two vertices. It’s the maximum number of
edges needed to connect the most distant pair.
• Eigenvalues: For a graph’s adjacency matrix A (where Aij = 1 if i and j are adjacent, 0 otherwise),
the eigenvalues are the graph’s “spectral signature.” The number of distinct eigenvalues, k, often
correlates with structural properties like symmetry or connectivity.
• To find: Graphs for which d = k − 1.

1 Path Graphs
A path graph Pn has n vertices in a line: v1 − v2 − · · · − vn . An example adjacency matrix for path graph
is:  
0 1 0 0
1 0 1 0
AP4 = 0 1 0 1


0 0 1 0
From v1 to vn , the shortest path (diameter) is n − 1 edges.[(i)]
The eigen values for A are given by:
 
kπ
λk = 2 cos , k = 1, 2, . . . , n
n+1
Consider two eigenvalues λi and λj corresponding to k = i and k = j, where i ̸= j. If λi = λj , then:
2(1 − cos(πi/n)) = 2(1 − cos(πj/n))
cos(πi/n) = cos(πj/n)
However, for i ̸= j, this equality cannot hold for 0 ≤ i, j < n unless i = j, which contradicts our
assumption. Thus, all eigenvalues are distinct.
The number of distinct eigenvalues is n. [(ii)]
Thus, from (i) and (ii), diameter = t-1 (where t is the number of distinct eigen values)

2 Simple Cycle Graphs

A simple cycle Cn forms a loop: v1 − v2 − · · · − vn − v1 . An example adjacency matrix for simple cycle
graph is:  
0 1 0 0 1
1 0 1 0 0
 
AC5 =  0 1 0 1 0
0 0 1 0 1
1 0 0 1 0

1
 The diameter depends on n as:
• n even: d = n/2 [(iii)]
• n odd: d = ⌊n/2⌋ [(iv)]
The eigen values of A are given by:
 
2πj
λj = 2 cos , j = 0, 1, . . . , n − 1
n
For a given i, the eigenvalue is:  
2πi
λi = 2 cos
n
Using the symmetry property of the cosine function:

cos(θ) = cos(−θ)

     
2πi 2πi 2π(n − i)
λi = 2 cos = 2 cos − = 2 cos = λn−i
n n n
Thus, λi = λn−i .
For n even, there are n2 + 1 distinct eigenvalues because λ n2 is distinct from the others due to the
symmetry.[(v)]
For n odd, there are n+1
2 distinct eigenvalues because there is no middle value that repeats. [(vi)]
Thus, from (iii) and (v) (and similarly from (iv) and (vi)),
diameter = t-1 (where t is the number of distinct eigen values)

3 Complete Graphs
A complete graph Kn has all vertices connected. An example adjacency matrix for complete graph is:
 
0 1 1 1
1 0 1 1
AK 4 = 
1 1 0 1


1 1 1 0

Every pair is adjacent, so d = 1.

The eigen values of A are n − 1 with multiplicity 1 and −1 with multiplicity n − 1. Thus, the number of
distinct eigen values is 2.
Thus, diameter = t-1 (where t is the number of distinct eigen values)

4 Complete Bipartite Graphs

A complete bipartite graph Km,n has edges between two sets. An example adjacency matrix for complete
bipartite graph is:  
0 0 1 1 1
0 0 1 1 1
 
AK2,3 = 1 1 0 0 0

1 1 0 0 0
1 1 0 0 0
For any two vertices u ∈ X and v ∈ Y , there is a direct edge between them. Thus, the distance between
u and v is 1. For any two vertices u, w ∈ X (or both in Y ), there is no direct edge between them because
the graph is bipartite. However, we can reach w from u by moving to a vertex in Y and then back to w. For
example, if v ∈ Y , then the path u → v → w has length 2.

2
 Thus, diatmeter = 2 √ √
The eigen values of A are mn, − mn, 0 with multiplicity m + n − 2. Thus, the number of distinct
eigenvalues is 3.
Thus, diameter = t-1 (where t is the number of distinct eigen values)

5 Distance-Regular Graphs
A distance-regular graph has uniform distance properties. An example adjacency matrix for distance
regular graph is:  
0 1 0 0 1 1 0 0 0 0
1 0 1 0 0 0 1 0 0 0
 
0 1 0 1 0 0 0 1 0 0
 
0 0 1 0 1 0 0 0 1 0
 
1 0 0 1 0 0 0 0 0 1
APetersen = 
1 0 0 0 0 0

 1 0 0 1
0 1 0 0 0 1 0 1 0 0
 
0 0 1 0 0 0 1 0 1 0
 
0 0 0 1 0 0 0 1 0 1
0 0 0 0 1 1 0 0 1 0
Let Γ be a distance-regular graph with diameter d. The adjacency matrix A of Γ satisfies:

A2 = kI + a1 A + c2 A2

where k is the valency, a1 and c2 are constants, and A2 represents the matrix of vertices at distance 2.
The eigenmatrix P of Γ is a (d + 1) × (d + 1) matrix where the l-th column consists of the eigenvalues of
Al . The eigenmatrix satisfies:
AP = P D
where D is a diagonal matrix containing the eigenvalues of A.
Since Γ is distance-regular, the eigenvalues of A are related to the intersection numbers. Each column
of P corresponds to a different distance matrix Al , and these matrices are linearly independent. Thus, the
number of distinct eigenvalues for a distance-regular graph is d + 1.
Thus, diameter = t-1 (where t is the number of distinct eigen values)

6 Conclusion
Examples of graphs for which he pattern d = k − 1 holds true are path graphs, simple cycle graphs, complete
graphs, complete bipartite graphs and distance- regular graphs.