Minimum dominating Randic energy of a graph
Автор: Reddy P.S.K., Prakasha K.N., Siddalingaswamy V.M.
Журнал: Владикавказский математический журнал @vmj-ru
Статья в выпуске: 2 т.19, 2017 года.
Бесплатный доступ
In this paper, we introduce the minimum dominating Randic energy of a graph and computed the minimum dominating Randic energy of graph. Also, obtained upper and lower bounds for the minimum dominating Randic energy of a graph.
Minimum dominating set, minimum dominating randic eigenvalues, minimum dominating randic energy
Короткий адрес: https://sciup.org/14318571
IDR: 14318571 | DOI: 10.23671/VNC.2017.2.6506
Текст научной статьи 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,..., vn} 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)nXn 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 A1 > A2 >
-
••• > Ar. with their 1 nultiplicil.ies m1,m2, ... ,mr. 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. a0 = 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 a2 = E 16i aii aji aij ajj E aiiajj— 16i aj iaij E aiiajj - 16i ^2 Wd = |D|C2 — P. ▻ 16i Proposition 3.2. If A1, A2,...,An 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,A2 , ...,An be the eigenvalues of RD (G). Now by Cauchy-Schwartz inequality we have (n \ 2 / n \ / n \ £ a-b- 6 £a-2 £b-2 -=1 -=1 -=1 Let a- = 1. bi =| Ai |. Then . n \ 2П n \ П n \ ElA-I 6 E1 EN1 , -=1 / \j=1 / \j=1 / [RED]2 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 \ 2n n / n \ £ I A- | =£ | A- |£| Aj |= £| A- I2 +£ 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)]2 > X | A- |2 +n(n - 1) (П I A- || Aj |j -=1 -=j n n n(n1-1) > £|A-^ +n(n - 1) nIA-^(n-1) -=1 -=1 = £ I A- |2 +n(n - 1)Rn = (|D| + 2P) + n(n - 1)R2. -=1 Thus, RED(G) > (|D| + 2P) + n(n - 1)R2. ▻ Theorem 4.1. The minimum dominating Randic energy of a complete graph Kn is RED (Kn) = 3n-5. C Lel, Kn be the complete gr;iph with vertex set V = {vi, V2,..., vn}. The minimum dominating set = D = {v1}. 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(Kn) = 3^-15. B Theorem 4.2. The minimum dominating Randic energy of star graph K1,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+ 5 2 n — 1^5 2 I . Therefore, RED(K1,n-1) = V5- B Теорема 4.3. The minimum dominating Randic energy of Crown graph Sn is RED (Sn0 ) = (4n — 7) + V 4n2 — 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) = (4n-7)±V4n2-8n±5. в Theorem 4.4. The minimum dominating Randic energy of complete bipartite graph Kn,nof оrder 2n with vertex set {u1, u2,..., un, v1, v2,..., 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 (Knn) = n vn n n vn . 1 1 1 2n - 4 1 / Therefore, RED(Knn) = 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(Fn3) = 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(Fn3) = n + 1. B Теорема 4.6. The minimum dominating Randic energy of Cocktail party graph Knx2is RED (KnX2) = 4n — 6 n . — 1 C Lel, KnX2 be a Cocktail par I,у graph of order 2n with vertex set {u1 ,u2,... ,un,v1,v2,..., vn}. 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-6. 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.
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) =
Список литературы Minimum dominating Randic energy of a graph
- Bozkurt S. B., Gungor A. D., Gutman I., Cevik A. S. Randic matrix and Randic energy//MATCH Commum. Math. Comput. Chem. 2010. Vol. 64. P. 239-250.
- Bozkurt S. B., Gungor A. D., Gutman I. Randic spectral radius and Randic energy//MATCH Commum. Math. Comput. Chem. 2010. Vol. 64. P. 321-334.
- Serife Burcu Bozkurt, Durmus Bozkurt. Sharp Upper Bounds for Energy and Randic Energy // MATCH Commum. Math. Comput. Chem. 2013. Vol. 70. P. 669-680.
- Gutman I., Furtula B., Bozkurt S. B. On Randic energy//Linear Algebra Appl. 2014. Vol. 442. P. 50-57.
- Gutman I. The energy of a graph//Ber. Math. Stat. Sekt. Forschungsz. Graz. 1978. 103. P. 1-22.
- Gutman I. The energy of a graph: old and new results//Combinatorics and applications/A. Betten, A. Khoner, R. Laue and A. Wassermann, eds. Berlin: Springer, 2001. P. 196-211.
- Indulal G., Gutman I., Vijayakumar A. On distance energy of graphs//Match Commun. Math. Comput. Chem. 2008. Vol. 60. P. 461-472.
- Rajesh Kanna M. R., Dharmendra B. N., Sridhara G. Minimum dominating energy of a graph//Int. J. Pure and Appl. Math. 2013. Vol. 85, № 4. P. 707-718.