Minimum dominating Randic energy of a graph

Let G be a simple, finite, undirected graph, The energy E(G) is defined as the sum of the absolute values of the eigenvalues of its adjacency matrix. For more details on energy of graphs (see [5, 6]).

The Randic matrix R(G) = (Rij)_nxn is given by Bozkurt et al. [1-3].

R

-I ij 1

1 didi ^,

0,

if Vi ~ Vj. otherwise.

We can see lower and upper bounds on Randic energy in [1, 2, 4]. Some sharp upper bounds for Randic energy of graphs were obtain in [3].

2.    The Minimum Dominating Randic Energy of Graph

Let G be a simple graph of order n with veil,ex sol, V = {vi, V2, V3,..., v_n} and edge set E. A subset D of V = V (G) is called a dominating set if every vertex in V — D adjacent to a vertex of D. Minimum dominating set is called a dominating set of minimum power. Let D be a. minimum dominating set of a. graph G. The minimum dominating Randic matrix RD(G) = (RD)n_Xn is given by

R

D ij

' 1

Vdidi ’

* 1,

.0,

if Vi ~ Vj.

if i = j arid vi G D. otherwise.

The characteristic polynomial of RD(G) is denoted by фR (G, A) = det(AI — RD(G)). Since the minimum dominating Randic Matrix is real and symmetric, its eigenvalues are

real numbers and we label them in non-increasing order A1 > A2 > ... An. The minimum dominating Randic Energy is given by

n

RE d (G) = £|М                        (1)

i=1

Definition 2.1. The spectrum of a graph G is the list of distinct eigenvalues A₁ > A₂ >

• ••• > Ar. with their 1 nultiplicil.ies m₁,m₂, ... ,m_r. and we write it as

• 3.    Some Basic Properties of Minimum Dominating Randic Energy of a Graph

A1    A2 . . .    Ar

Spec(G) =                     .

m1 m2 . . . mr

This paper is organized as follows. In the Section 3, we get some basic properties of minimum dominating Randic energy of a. graph. In the Section 4, minimum dominating Randic energy of some standard graphs are obtained.

Let us consider

P=5 w i

Where didj is the product of degrees of two vertices which are adjacent.

Proposition 3.1. The first three coefficients of фD(G, A) are given as follows:

(!) ao = 1.

• (n) ai = — |D| .

• (ш) a2 = |DC - P.

C (i) From the definition ФD(G, A) = det[AI — RD(G)]. we gel. a₀ = 1.

(h) The sum of determinants of all 1 x 1 principal sul.matrices of RD(G) is equal to the trace of RD(G).

^ a1 = ( —1)1 tracо of [RD(G)] = — |D|.

(iii)

^{( —1)2 a}2 =  E

16i

aii

aji

aij ajj

E  aiiajj^—

16i

aj iaij

E  aiiajj -

16i

^2 Wd = |D|C2 — P. ▻

16i

Proposition 3.2. If A₁, A₂,...,A_n are the minimum dominating Randic eigenvalues of RD (G). then n

X Ai2 = |D| +2P.

i=1

C We know that n    nn              n

E A2 = E Е<^aji = 2E(aij )2 + №2 = 2E(aj)2 + |D| = |D| + 2P ▻

• i=1       i=1 j=1            i

  Theorem 3.1. Let G be a graph with n vertices and then RED(G) 6 pnM+TPD,

  
  

  where

  
  

  ^P= dj

  i

  for which didj is the product of degrees of two vertices which are adjacent.

  C Let A1,A₂ , ...,An be the eigenvalues of RD (G). Now by Cauchy-Schwartz inequality we have

  
  

  (n \ ²    / n \ / n \

  £ a-b-   6 £a-²   £b-²

  -=1              -=1         -=1

  Let a_- = 1. bi =| Ai |. Then

  
  

  .

  
  

  n     \ ²П n   \  П n      \

  ElA-I 6 E1  EN¹ ,

  -=1    /      \j=1  /  \j=1     /

  [RED]² 6 n(|D| +2P),

  [RED] 6 Pn(|D| +2P),

  
  

  which is upper bound. B

  Theorem 3.2. Let G be a graph with n vertices. RR = det RD(G), then

  RED(G) >  (|D| + 2P)+ n(n - 1)Rn.

  
  

  C By definition.

  
  

  (n      \ ²n        n          / n       \

  £ I A- |   =£ | A- |£| Aj |= £| A- I² +£ I A- II Aj I .

  -=1              -=1       j=1          \-=1       /    -=j

  
  

  Using arithmetic mean and geometric mean inequality, we have

  
  

  г X I Ai || Ay |> n(n - 1)       ^{1 - 11 j}

  -=j

  
  

  | λi || λj |

  -=j

  
  

  Therefore,

  
  

  1 n(n-1)

  
  

  i

  n                           /                  \ n(n-1)

  [RED(G)]² > X | A- |² +n(n - 1) (П I A- || Aj |j

  • -=1                        -=j

  n                              n                   n(n¹-1)

  • > £|A-^ +n(n - 1) nIA-^^(n-1)

  -=1                      -=1

  
  

  = £ I A- |² +n(n - 1)Rn = (|D| + 2P) + n(n - 1)R².

  -=1

  
  
4. Minimum Dominating Randic Energy of Some Standard Graphs

Thus,

RED(G) >   (|D| + 2P) + n(n - 1)R2. ▻

Theorem 4.1. The minimum dominating Randic energy of a complete graph K_n is RED (Kn) = 3n-5.

C Lel, Kn be the complete gr;iph with vertex set V = {vi, V2,..., v_n}. The minimum dominating set = D = {v₁}. The minimum dominating Randic matrix is

	- 1        1        1                  1        1 - n-1 n-1    . . .    n-1   n-1 1     1     11 n-1           n-1    . . .    n-1   n-1
RD(Kn) =	n-1   n-1     v     •• • n-1   n-1 ■                      ■                      ■                  e                         •                      • •                      •                      •                         *                  •                      • 0 n-1   n-1    . . .    n-1           n-1 11   11 n-1   n-1    . . .    n-1   n-1

Characteristic equation is

A +

n-

n-2

λ2

-

2n - 3

n

-1

A+

n — 3 n-1

= 0

and the spectrum is

SpecD (Kn)

(2n-3)+^√4n-3   (2n-3)-^√4n-3

2(n-1)            2(n-1)

-1 n-1

n-2

Therefore. RED(K_n) = 3^-15. B

Theorem 4.2. The minimum dominating Randic energy of star graph K₁,_n-1is

RED (Ki,n-i) = V5.

C Let Ki,n-i be the star graph with vertex set V = {vi, V2,..., vn}. Here vo be the center. The minimum dominating set = D = {v0}. The minimum dominating Randic matrix is

Characteristic equation is

(A)n-2[A2 — A — 1] =0

RD (Ki,n-i) =

1 1 1 1 1 √n-1 √n-1   . . .   √n-1 √n-1 1 0 0     .. .0 0 √n-1 1 0 0     .. •                        . .0 0 1 Cn-1 • • 1 0 0     .. .0 1 0 √n-1 1 0 0     .. .0 0 √n-1 spectrum is SpecD (K1,n-1) =

1+ 5 2

n —

1^5

2 I . Therefore, RED(K₁,_n-1) = V5- B

Теорема 4.3. The minimum dominating Randic energy of Crown graph Sn is

RE^D (Sn⁰ ) =

(4n — 7) + V 4n² — 8n + 5 n — 1

C Lel, Sn L>e a crown graph of order 2n with vertex sol, {ui,u2,..., un, vi, V2,..., vn} and minimum dominating set = D = {ui, vi}. The minimum dominating Randic matrix is

1     0      0    ...    0      0      1     ...     1      1 . . .                      n-1    . . .    n-1    n-1 0   0   0  ...  0        0   ...  — — . . .            n-1             . . .    n-1    n-1 0      0      0    ...    0      1     ...     1      0      1 . . .            n-1    . . .n-1             n-1 •                      •                      ■                e                       •                      •                      ■                  e                         •                      •

RD (Sn0 ) =

•                      •                      •                   •                    •                      •                      •                      •                      •                      • •                      •                      •                       *                •                      •                      •                         *                  •                      • 0   0   0  ...  0        ... — —  0 . . .            n-1    . . .    n-1 n-1 0         Л ...         1    0   ...    0    0 n-1    n-1 . . .n-1                        . . . 1      0      1    ...    1      0      0     ...     0      0 n-1          n-1        n-1 •                      •                      ■                e                       •                      •                      ■                  e                         •                      • •                      •                      •                   •                    •                      •                      •                      •                      •                      • •                      •                      •                       *                •                      •                      •                         *                  •                      • n-Г  n-T   0   ...  nb   0    0    ...    0    0 n-11   n-11   n-11   ...    0      0      0     ...     0      0

Characteristic equation is

^           2 (^— n—1

1 n—1

n-2

λ2

—

n—1

λ

—

λ

—

2n — 3

n—1

λ+

n

—3

n—1

=0

spectrum is

SpecRD (Sn0)

(2n-3)+√4n-3 2(n-1)

1+√4n2 -8n+5 2(n-1)

(2n-3)-√4n-3 2(n-1)

1       -1

n-1    n-1

n—2 n—2

1-√4n2 -8n+5 2(n-1)

Therefore. RED(Sn) = ⁽⁴ⁿ-⁷⁾±V4n^2-8n±5. в

Theorem 4.4. The minimum dominating Randic energy of complete bipartite graph

Kn,nof оrder 2n with vertex set {u₁, u₂,..., un, v₁, v₂,..., vn} is

RED (Kn,n) = 2 V—^ +2. n

C Let Kn,n be the complete bipartite graph of order 2n with vertex set {u1, u2,..., un, v1, v2,..., vn}. The minimum dominating sei, = D = {u1, v1}. The minimum dominating Randic matrix is

	100	0 ...1 1	11
		nn	nn
	0 0 0	0 ...1 1	1  1
		...n n	n n
	0 0 0	0 ...1 1	1  1
		...n n	nn
	0 0 0	0 ...1 1	1  1
		... n n	n n
RD(Kn,n) =	•             •             • •             •             • •             •             •	1 • • ♦ • • • • * • •	♦             • ♦             • ♦             •
	111	1... 1 0	0 0
	n n n	n ...
	111	1... 0 0	0 0
	nnn	n
	111	1... 0 0	0 0
	nnn	n
	111	1... 0 0	00
	nnn	n
Characteristic equation is
λ2n-4  λ2	n-1	D - 2Л + n-11	= 0.
	n	n

1 + - /1 Vn-i 1 -. /1    о    - vn-r

Hence, spectrum is SpecD (K_nn) =           ^{n   v}n       n ^{n             v}n    .

1        1        1     2n - 4     1    /

Therefore, RED(K_nn) = ^2vVE1 + 2. B

Definition 4.1. The friendship graph, denoted by F^n), is the graph obtained by taking n copies of the cycle graph C3 with a vertex in common. V(Fn) = 2n + 1.

Теорема 4.5. The minimum dominating Randic energy of Friendship graph Fn is

RED(F_n³) = n+ 1.

(n)

C Lel, F3 ' be the friend ship graph with 2n + 1 vertices. Here vi be the center. The minimum dominating set = D = {vi}. The minimum dominating Randic matrix is

	■ 1	1	1	1	1	1	1
		2√n	2√n	2√n	2√n   . . .	2√n	2√n
	1 2Vn	0	1 2	0	0    ...	0	0
	1 2Vn	1 2	0	0	0    ...	0	0
RD (Fn3 ) =	1 2Vn 1 2Vn • •	0 0 . .	0 0 . .	0 1 2 . .	1 2     ... 0    ... 1                    - 1                         •	0 0	0 0 1 1
	• 1 2√n	. 0	. 0	. 0	•                             • 0    ...	0	1 1 2
	1 2√n	0	0	0	0    ...	1 2	0

Characteristic equation is

Va + 1 VC -1 Г'^ - 3) = 0. 222

Hence, spectrum is

3      1-1

SpecD(F3)=   2    2    0   2.

^{R n}     1 n — 11 n

Therefore. RED(Fn³) = n + 1. B

Теорема 4.6. The minimum dominating Randic energy of Cocktail party graph K_nx2is

RED (Kn_X2) =

4n — 6

n

.

— 1

C Lel, K_nX2 be a Cocktail par I,у graph of order 2n with vertex set {u1 ,u₂,... ,u_n,v1,v₂,..., v_n}. The minimum dominating set = D = {u1, v1}. The minimum dominating minimum dominating Randic matrix is

	111   111 x     2n-2   2n-2   2n-2   . . .     v     2n-2   2n-2   2n-2 2n-2     u     2n-2   2n-2   • • •   2n-2     u     2n-2   2n-2 2n-2   2n-2     v     2n-2   ‘ ‘ ‘   2n-2   2n-2     v     2n-2 _^_ _ _ o              0 2n-2   2n-2   2n-2     u     . . .   2n-2   2n-2   2n-2     u •                         •                         •                         •                  •                         •                         •                         •                         • •                         •                         •                         •                     •                     •                         •                         •                         • •                         •                         •                         •                         *                  •                         •                         •                         • 0                                    1 v     2n-2 2n-2 2n-2 . . .           2n-2 2n-2 2n-2 2n-2     v     2n-2   2n-2   ‘ ‘ ‘   2n-2     v     2n-2   2n-2 2n-2   2n-2     v     2n-2   ‘ ‘ ‘   2n-2   2n-2     v     2n-2 111   111 2n-2   2n-2   2n-2    u    ..^  2n-2   2n-2   2n-2    u tion is 'A + -4-)   (A — 1) [a2 — 2n—3A + n-^ 1 = 0. 4 n — 1 /                 n — 1     n — 1
RD (Knx2) =
Characteristic equa An-1 (

Hence, spectrum is

SpecD (Knx2) =

2n-3+V4n-3

2(n-1)

2n - 3 -V4n-3 2(n-1)

n—1

-1 n—1 n—2

Therefore. RED(Knx2) = -f-⁶. B

Acknowledgement. The authors are thankful to the anonymous referee for valuable suggestions and comments for the improvement of the paper. Also, the first author is grateful to Dr. M. N. Channabasappa, Director and Dr. Shivakumaraiah, Principal, Siddaganga Institute of Technology, Tumkur, for their constant support and encouragement.