# The Distance Matrices of Some Graphs Related to Wheel Graphs

Authors: Xiaoling Zhang; Chengyuan Song
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

LetD denote the distance matrix of a connected graph G. The inertia of D is the triple of integers (n+(D),n0(D),n-(D)), where n+(D), n0(D), and n-(D) denote the number of positive, 0, and negative eigenvalues of D, respectively. In this paper, we mainly study the inertia of distance matrices of some graphs related to wheel graphs and give a construction for graphs whose distance matrices have exactly one positive eigenvalue.


---

## Body

## 1. Introduction

A simple graph
G
=
(
V
,
E
) consists of V, a nonempty set of vertices, and E, a set of unordered pairs of distinct elements of V called edges. All graphs considered here are simple and connected. Let G be a simple connected graph with vertex set V(G) and edge set E(G). The distance between two vertices u, v∈V(G) is denoted by duv and is defined as the length of the shortest path between u and v in G. The distance matrix of G is denoted by D(G) and is defined by D(G)=(duv)u,v∈V(G). Since D(G) is a symmetric matrix, its inertia is the triple of integers (n+(D(G)),n0(D(G)),n-(D(G))), where n+(D(G)), n0(D(G)), and n-(D(G)) denote the number of positive, 0, and negative eigenvalues of D(G), respectively.The distance matrix of a graph has numerous applications to chemistry [1]. It contains information on various walks and self-avoiding walks of chemical graphs. Moreover, the distance matrix is not only immensely useful in the computation of topological indices such as the Wiener index [1] but also useful in the computation of thermodynamic properties such as pressure and temperature virial coefficients [2]. The distance matrix of a graph contains more structural information compared to a simple adjacency matrix. Consequently, it seems to be a more powerful structure discriminator than the adjacency matrix. In some cases, it can differentiate isospectral graphs although there are nonisomorphic trees with the same distance polynomials [3]. In addition to such applications in chemical sciences, distance matrices find applications in music theory, ornithology [4], molecular biology [5], psychology [4], archeology [6], sociology [7], and so forth. For more information, we can see [1] which is an excellent recent review on the topic and various uses of distance matrices.Since the distance matrix of a general graph is a complicated matrix, it is very difficult to compute its eigenvalues. People focus on studying the inertia of the distance matrices of some graphs. Unfortunately, up to now, only few graphs are known to have exactly one positiveD-eigenvalue, such as trees [8], connected unicyclic graphs [9], the polyacenes, honeycomb and square lattices [10], complete bipartite graphs [11], Kn, and iterated line graphs of some regular graphs [12], and cacti [13]. This inspires us to find more graphs whose distance matrices have exactly one positive eigenvalue.Thewheel graph of n vertices Wn is a graph that contains a cycle of length n-1 plus a vertex v (sometimes called the hub) not in the cycle such that v is connected to every other vertex. In this paper, we first study the inertia of the distance matrices in wheel graphs if one or more edges are removed from the graph, and then, with the help of the structural characteristics of wheel graphs, we give a construction for graphs whose distance matrices have exactly one positive eigenvalue.


## 2. Preliminaries

We first give some lemmas that will be used in the main results.Lemma 1 (see [14]).
LetA be a Hermitian matrix with eigenvalues λ1⩾⋯⩾λn and B one of its principal submatrices. Let B have eigenvalues μ1⩾⋯⩾μm. Then the inequalities λn-m+i⩽μi⩽λi(i=1,…,m) hold.For a square matrix, letcof(A) denote the sum of cofactors of A. Form the matrix A~ by subtracting the first row from all other rows then the first column from all other columns and let A~11 denote the principle submatrix obtained from A~ by deleting the first row and first column.Lemma 2 (see [15]).
c
o
f
(
A
)
=
det
A
~
11.
Acut vertex is a vertex the removal of which would disconnect the remaining graph; a block of a graph is defined to be a maximal subgraph having no cut vertices.Lemma 3 (see [15]).
IfG is a strongly connected directed graph with blocks G1,G2,…,Gr, then
(1)cofD(G)=∏i=1r‍cofD(Gi),detD(G)=∑i=1r‍detD(Gi)∏j≠i‍cofD(Gi).Lemma 4.
Let(2)C=[1111⋯11-1-2-10⋯000-1-2-1⋯0000-1-2⋯00⋮⋮⋮⋮⋱⋮⋮0000⋯-2-10000⋯-1-2]n×n.
Then
(3)detC={-n2,ifniseven,n+12,ifnisodd.Proof.
Let(4)Cn=|1111⋯11-1-2-10⋯000-1-2-1⋯0000-1-2⋯00⋮⋮⋮⋮⋱⋮⋮0000⋯-2-10000⋯-1-2|n×n,Dn=|12-100⋯001-2-10⋯001-1-2-1⋯0010-1-2⋯00⋮⋮⋮⋮⋱⋮⋮1000⋯-2-11000⋯-1-2|n×n.
Comparing Cn to Dn, we get the following:
(5)Cn=Dn+n2×(-1)n-1.
Expanding the determinant Dn according to the last column and then the last line, we get the following incursion:
(6)Dn=-2Dn-1-Dn-2+1;
that is,
(7)Dn+Dn-1=-(Dn-1+Dn-2)+1.
Since D1=1/2, D2=0, and D3=1/2, from the above incursion, we get the following:
(8)Dn={0,ifnis  even,12,ifnis  odd.
So, we have the following:
(9)Cn={-n2,ifnis  even,n+12,ifnis  odd.
This completes the proof.


## 3. Main Results

In the following, we always assume thatV(Wn)={v0,v1,…,vn-1}, where v0 is the hub of Wn.Theorem 5.
Lete=vivi+1mod(n-1)(1⩽i⩽n-1). Then
(10)detD(Wn-e)={-n24,ifniseven,n2-14,ifnisodd,
where n⩾3.Proof.
Without loss of generality, we may assume thate=v1vn-1. Let
(11)An=detD(Wn-e)=|0111⋯111012⋯221101⋯221210⋯22⋮⋮⋮⋮⋱⋮⋮1222⋯011222⋯10|n×n.
Then(12)An=|011-121⋯111-200⋯001-120-2+12-1⋯0010-1-2⋯00⋮⋮⋮⋮⋱⋮⋮1000⋯-2-11000⋯-1-2|n×n.
Expanding the determinant An according to the second line, we get the following incursion:
(13)An=(-1)n-1n2-2An-1-Cn-2-Dn-2-An-2,
where Cn and Dn are defined as in Lemma 4.
By Lemma4, we get the following:
(14)An={-1-2An-1-An-2,ifnis  even,-2An-1-An-2,ifnis  odd.
Since A3=2, A4=-4, A5=6, and A6=-9, according to the above incursion, we get the following:
(15)An={-n24,ifnis  even,n2-14,ifnis  odd,
where n⩾3. This completes the proof.Corollary 6.
Lete=vivi+1mod(n-1)(1⩽i⩽n-1). Then
(16)n+(D(Wn-e))=1,n0(D(Wn-e))=0,n-(D(Wn-e))=n-1.Proof.
We will prove the result by induction onn.
Ifn=3, W3-e≅P3  is obviously true.
Suppose that the result is true forn-1; that is, n+(D(Wn-1-e))=1, n0(D(Wn-1-e))=0, n-(D(Wn-1-e))=n-2.
SinceD(Wn-1-e) is a principle submatrix of D(Wn-e), by Lemma 1, the eigenvalues of D(Wn-1-e) interlace the eigenvalues of D(Wn-e). By Theorem 5, detD(Wn-1-e)detD(Wn-e)<0. So, D(Wn-e) has one negative eigenvalue more than D(Wn-1-e). According to the induction hypothesis, we get n+(D(Wn-e))=1, n0(D(Wn-e))=0, and n-(D(Wn-e))=n-1. This completes the proof.Theorem 7.
One has(17)detD(Wn)={1-n,ifniseven,0,ifnisodd,
where n⩾3.Proof.
Consider the following(18)detD(Wn)=|0111⋯111012⋯211101⋯221210⋯22⋮⋮⋮⋮⋱⋮⋮1222⋯011122⋯10|n×n=|0111⋯111-2-10⋯0-11-1-2-1⋯0010-1-2⋯00⋮⋮⋮⋮⋱⋮⋮1000⋯-2-11-100⋯-1-2|n×n=|0n-111⋯11n-1-4(n-1)-4-4⋯-4-41-4-2-1⋯001-4-1-2⋯00⋮⋮⋮⋮⋱⋮⋮1-400⋯-2-11-400⋯-1-2|n×n=|0n-111⋯11n-14(n-1)00⋯0010-2-1⋯0010-1-2⋯00⋮⋮⋮⋮⋱⋮⋮1000⋯-2-11000⋯-1-2|n×n.
Expanding the above determinant according to the second line, we get the following:
(19)detD(Wn)=(-1)n-1(n-1)3+4(n-1)An-1,
where An is defined as in Theorem 5.
By Theorem5, when n⩾3, we get the following:
(20)detD(Wn)={1-n,ifnis  even,0,ifnis  odd.
This completes the proof.Similar to Corollary6, we can get the following corollary.Corollary 8.
(i)  Ifn is even, n+(D(Wn))=1, n0(D(Wn))=0, n-(D(Wn))=n-1.
(ii)  Ifn is odd, n+(D(Wn))=1, n0(D(Wn))=1, n-(D(Wn))=n-2.
Denote byWn-v0 the graph obtained from Wn by deleting the vertex v0 and all the edges adjacent to v0; that is, Wn-v0≅Cn-1. Let Ek(1⩽k⩽n) be any subset of E(Wn-v0) with |Ek|=k. In the following, we always denote by Wn-Ek the graph obtained from Wn by deleting all the edges in Ek.Theorem 9.
One hasn+(D(Wn-Ek))=1, n0(D(Wn-Ek))=0, n-(D(Wn-Ek))=n-1.Proof.
Denote the components ofWn-Ek-v0 by C1,…,Cs. Let Gi denote the graph that contains Ci plus the vertex v0 such that v0 is connected to every other vertex, 1⩽i⩽s. Then each Gi(1⩽i⩽s) is isomorphism to W|V(Gi)|-ei or K2, where ei is an edge of W|V(Gi)|-v0. By Lemma 2 and some direct calculations, we get the following:
(21)cof(Gi)=detD(W|V(Gi)|-ei)~11=(-1)|V(Gi)|-1|V(Gi)|.
It is easy to check that cof(Gi)=(-1)|V(Gi)|-1|V(Gi)| is also true when Gi is isomorphism to K2.
In the following, we will prove the theorem by introduction ons.
Fors=1, G≅Wn-e, where e is an edge of Wn-v0, by Corollary 6, we get the result.
Suppose the result is true fors-1.
Fors, let G′=G1∪G2∪⋯∪Gs-1. Then by the induction hypothesis, n+(D(G′))=1, n0(D(G′))=0, and n-(D(G′))=|V(G′)|-1, which implies that
(22)detD(G′)=(-1)|V(G′)|-1a,
where a is a positive integer.
Since(23)cof(Gi)=(-1)|V(Gi)|-1|V(Gi)|,1⩽i⩽s,
by Lemma 3,
(24)cofD(G′)=∏j=1s-1‍cofD(Gj)=(-1)|V(G′)|-1∏j=1s-1‍|V(Gj)|.
Then(25)detD(Wn-Ek)=detD(G′)cofD(Gi)+detD(Gi)cofD(G′)=(-1)|V(G′)|-1a×(-1)|V(Gi)|-1|V(Gi)|+(-1)|V(Gi)|-1b×(-1)|V(G′)|-1∏j=1s-1‍|V(Gj)|=(-1)n-1(a|V(Gi)|+b∏j=1s-1‍|V(Gj)|),
where b=n2/4, if n is even and b=(n2-1)/4, if n is odd.
In this case, similar to Corollary6, we can easily get n+(D(Wn-Ek))=1, n0(D(Wn-Ek))=0, and n-(D(Wn-Ek))=n-1.
Up to now, we have proved the result.LetGui·vjH denote the graph formed by only identifying the vertex ui of G with the vertex vj of H, where ui and vj are arbitrary vertices of G and H, respectively.Lemma 10 (see [13]).
LetG×H denote the Cartesian product of connected graphs G and H, where V(G)={u1,…,um} and V(H)={v1,…,vn}. Then we have(i)
n+(G×H)=n+(Gui·vjH);(ii)
n0(G×H)=(m-1)(n-1)+n0(Gui·vjH);(iii)
n-(G×H)=n-(Gui·vjH).Theorem 11.
Letu0 and v0 be the hubs of Wn and Wm, respectively. Suppose Ep(0⩽p⩽n-1) and Eq(0⩽q⩽m-1) are any subsets of E(Wn-u0) and E(Wm-v0) with |Ep|=p, |Eq|=q, respectively. Then, the distance matrix of the graph (Wn-Ep)×(Wm-Eq) has exactly one positive eigenvalue.Proof.
Sinceu0 and v0 are the hubs of Wn and Wm, respectively, (Wn-Ep)u0·v0(Wm-Eq) must be isomorphism to some Wn+m-1-Ep+q, where w0 is the hub of Wn+m-1 and Ep+q is any subset of E(Wn+m-1-w0) with |Ep+q|=p+q. By Theorem 9 and Lemma 10, we get the result.Given an arbitrary integerm, for 1⩽i⩽m, let vi0 be the hub of Wni and Epi any subset of E(Wni-vi0). Suppose V(Wni)={vi0,vi1,…,vi(ni-1)}.Theorem 12.
For an arbitrary integerm, the distance matrix of the graph G=(Wn1-Ep1)v1k·v2j(Wn2-Ep2)v2h⋯v(m-1)r(Wnm-1-Epm-1)v(m-1)t·vms(Wnm-Epm) has exactly one positive eigenvalue.Proof.
We will prove the conclusion by induction onm.
Ifm=1, by Theorem 9, the conclusion is true.
Suppose the conclusion is true form-1. For convenience, let H=(Wn1-Ep1)v1k·v2j(Wn2-Ep2)v2h⋯v(m-2)i(Wnm-2-Epm-2). Then G=Hv(m-2)g·v(m-1)r(Wnm-1-Epm-1)v(m-1)t·vms(Wnm-Epm). By Lemma 10, we have the following:
(26)n+(G)=n+(H(Wnm-1-Epm-1)v(m-1)t·vms(Wnm-Epm))=n+(H(Wnm-1-Epm-1)v(m-1)0·vm0(Wnm-Epm)).
Since (Wnm-1-Epm-1)v(m-1)0·vm0(Wnm-Epm)=Wnm-1+nm-1-Epm-1-Epm, we get n+(G)=n+(Hv(m-2)g·v(m-1)r(Wnm-1+nm-1-Epm-1-Epm)). By the induction hypothesis, we get n+(G)=1. This completes the proof.Remark 13.
LetG1 and G2 be any two graphs with the same form as G in Theorem 12. Making Cartesian product of graphs G1 and G2, by Lemma 10 and Theorem 12, we get a series of graphs whose distance matrices have exactly one positive eigenvalue.



---

*Source: 707954-2013-06-15.xml*