3. SPECTRA OF VERTEX DISTANCE COMPLEMENT MATRIX

(VDC)

The eigenvalue of VDC(G)

is called the VDC – eigenvalue of the graph G. It is denoted by ?1

? ?2 ? … ? ?n. The set of all VDC – eigenvalues of G is called the VDC

– spectrum of G and is

denoted by VDCSpec(G). Two non isomorphic graphs are

said to be VDC – cospectral if they have the same VDC – spectrum.

Theorem 3.1. Let G be a r – regular graph on ‘n’

vertices and diam(G) = 2. Let { r = ?1, ?2, …, ?n}

be the adjacency eigenvalues of

G then VDC – eigenvalues of G are (n – 1)(n – 2) + r and ?i – n + 2 for i = 2, 3, … , n.

Proof. Given G is r – regular. We have r

is the largest eigenvalue of A = A(G). Let D = D(G) be the

distance matrix of the graph G.

Since diam(G) = 2,

D(G)

= A + 2

= A + 2(J – I – A)

= 2(J – I)

– A

From Definition 2.1 VDC – matrix, VDC(G)

can be written as,

VDC(G) = n(J – I) – D

= (n – 2)J – (n

– 2)I + A

= (n – 2)(J

– I) + A

Where J is an n n

matrix with all entries equal to 1 and I

is the identity matrix.

Using Lemma 2.1 we get the VDC – eigenvalues are (n

– 1)(n – 2) + r and ?i – n + 2

for i = 2, 3, …, n.

Theorem 3.2. Let G be a connected

r – regular graph with n

> 3 vertices and let none of

the three graphs Fi,

i = 1, 2, 3 of Figure.1 will be an induced subgraph of

G. Then VDC – spectrum of L(G) is

VDCSpec(L(G)) =

for i = 2, 3, …, n.

Proof. Let { r = ?1,

?2, …, ?n } be the adjacency spectrum of G. Then by Theorem 2.3 L(G), is a

(2r – 2) – regular graph with spectrum 2r

– 2, ?i + r – 2 for i = 2, 3, …, n

and -2 repeats

times.

Also Fi, i

= 1, 2, 3 is not an induced

subgraph of G, by Theorem

2.5, diam(L(G)) ? 2.

Hence by theorem 3.1 VDC – eigenvalues of L(G) are,

(– 1)( – 2) + 2r – 2 = ¼(n2r2

– 6nr + 8r) (1)

(?i + r – 2)

– + 2 = ½ (2?i

+ 2r – nr) for i =

2, 3, …, n (2)

– 2 – + 2 = – repeats times (3)

Theorem 3.3. Let G be a connected r

– regular graph with n > 3 vertices and for any two non

adjacent vertices ‘u’ and ‘v’

of a graph G, there exists a third vertex ‘w’ which is not adjacent to

either ‘u’ or ‘v’. Then

V DC – spectrum of is,

VDCSpec( =

for i = 2, 3, …, n.

Proof : Let { r = ?1, ?2, …, ?n

} be the adjacency spectrum of

G. Then by Theorem (2.4) , is a ( – 2r

+ 1) – regular graph on vertices

with spectrum – 2r + 1, – ?i – r + 1 for i =

2, 3, …, n and 1 repeats times.

By Theorem

3.1 the VDC – spectrum of is,

( – 1)( – 2) + – 2r +

1

-?i

–r + 1 – + 2 for i

= 2, 3, …, n

1 – + 2 = 3 – repeats

times.

ie,

()2 – nr – 2r + 3 = ¼ (n2r2 – 4nr – 8r +

12) (4)

-½ (2?i + 2r + nr – 6), for

i = 2, 3, …, n

(5)

3 – , repeats times (6)

Theorem 3.4. Let G be a connected

r – regular graph with n

> 3 vertices and let none of

the four graphs Fi, i = 1, 2, 3, 4 of Figure .1 will

be an induced subgraph of G. Then VDC – spectrum of

L2(G) is

VDCSpec(L2(G)) =

for i = 2, 3, …, n and k = .

Proof. Let { r = ?1,

?2, …, ?n } be the adjacency spectrum of G. Then

by Theorem 2.3 and Theorem 3.1 L2(G), is a (4r – 6) – regular graph on

k = vertices

with VDC –spectrum

(k – 1)(k – 2) + 4r – 6

(?i + 3r – 6) –

k + 2, for i=

2, 3, …, n

2r – 6 – k + 2, repeats times

– 2 – k + 2, repeats times

ie k2

– 3k + 4r – 4, where k = (7)

?i + 3r – k – 4, for

i=2, 3, …, n

(8)

2r – k – 4, repeats times (9)

-k, repeats times (10)