Minimum Covering Randić Energy of a Graph

M. R. Rajesh Kanna^1,2*, R. Jagadeesh³

¹Department of Mathematics, Government First Grade College, Puttur, India.
²Department of Mathematics, Maharani’s Science College for Women, Mysore, India.
³Research and Development Centre, Bharathiar University, Coimbatore, India.

DOI: 10.4236/alamt.2016.64012                

Abstract

Randić energy was first defined in the paper [1]. Using minimum covering set, we have introduced the minimum covering Randić energy RE_C (G) of a graph G in this paper. This paper contains computation of minimum covering Randić energies for some standard graphs like star graph, complete graph, thorn graph of complete graph, crown graph, complete bipartite graph, cocktail graph and friendship graphs. At the end of this paper, upper and lower bounds for minimum covering Randić energy are also presented.

Keywords

Minimum Covering Set, Minimum Covering Randić Matrix, Minimum Covering Randić Eigenvalues, Minimum Covering Randić Energy

1. Introduction

Study on energy of graphs goes back to the year 1978, when I. Gutman [2] defined this while working with energies of conjugated hydrocarbon containing carbon atoms. All graphs considered in this paper are assumed to be simple without loops and multiple edges. Let be the adjacency matrix of the graph with its eigenvalues assumed in decreasing order. Since A is real symmetric, the eigenvalues of G are real numbers whose sum equal to zero. The sum of the absolute eigenvalues values of G is called the energy of G. i.e.,

1.1. Randić Energy

It was in the year 1975, Milan Randić invented a molecular structure descriptor called Randić index which is defined as [11]

Motivated by this S.B. Bozkurt et al. [1] defined Randić matrix and Randić energy as follows. Let be graph of order n with vertex set and edge set E. Randić matrix of is a symmetric matrix defined by, where

The characteristic equation of is defined by. The roots of this equation is called Randić eigenvalues of G. Since is real and symmetric, its eigenvalues are real numbers and we label them in decreasing order. Randić energy of G is defined as

1.2. Minimum Covering Energy

In the year 2012 C Adiga et al. [15] introduced minimum covering energy of a graph, which depends on its particular minimum cover. A subset C of vertex set V is called a covering set of G if every edge of G is incident to at least one vertex of C. Any covering set with minimum cardinality is called a minimum covering set. If C is a minimum covering set of a graph G then the minimum covering matrix of G is the matrix defined by, where

The minimum covering eigenvalues of the graph G are roots of the characteristic equation, obtained from the matrix. Since is real and symmetric, its eigenvalues are real numbers and we label them in the order. The minimum covering energy of G is defined as

1.3. Minimum Covering Randić Energy

Results on Randić energy and minimum covering energy of graph G motivates us to define minimum covering Randić energy. Consider a graph G with vertex set and edge set E. If C is a minimum covering set of a graph G then the minimum covering Randić matrix of G is the matrix defined by,

where

The characteristic polynomial of is defined by . The minimum covering Randić eigenvalues of the graph G are the eigenvalues of. Since is real and symmetric matrix so its eigenvalues are real numbers. We label the eigenvalues in order. The minimum covering Randić energy of G is defined as

Example 1: i) ii) are the possible minimum cove- ring sets for the Figure 1 as shown below.

i)

Minimum covering Randić eigenvalues are

Minimum covering Randić energy,

Figure 1. Minimum covering Randić energy depends on the covering set.

ii)

Minimum covering Randić eigenvalues are

.

Minimum covering Randić energy,

Therefore minimum covering Randić energy depends on the covering set.

2. Main Results and Discussion

2.1. Minimum Covering Randić Energy of Some Standard Graphs

Theorem 2.1 For, the minimum covering Randić energy, of complete graph is

Proof. Let be a complete graph with vertex set. The mini- mum covering set for is. Then

Characteristic polynomial is

Characteristic equation is

Minimum covering Randić Spec

Minimum covering Randić energy,

Definition 2.1 Thorn graph of is denoted by and it is obtained by attaching one edge to each vertex of.

Theorem 2.2 For, the minimum covering Randić energy, of thorn

graph is

Proof. is a thorn graph of complete graph with vertex set . The minimum covering set for thorn graph is. Then

Characteristic polynomial is

.

Characteristic equation is

Minimum covering Randić Spec

Minimum covering Randić energy is,

Definition 2.2 Cocktail party graph is denoted by, is a graph having the vertex set and the edge set.

Theorem 2.3 The minimum covering Randić energy, of cocktail party graph is

Proof. Consider cocktail party graph with vertex set. The mi- nimum covering set of cocktail party graph is. Then

Characteristic polynomial is,

.

Characteristic equation is,

.

Minimum covering Randić Spec

Minimum covering Randić energy,

Theorem 2.4 For, minimum covering Randić energy, of star graph is equal to.

Proof. Let be a star graph with vertex set. Then its Minimum covering set is.

Characteristic equation is

Minimum covering Randić Spec

Minimum covering Randić energy,

Definition 2.3 Crown graph for an integer is the graph with vertex set and edge set.

Theorem 2.5 For, minimum covering Randić energy, of the crown graph is equal to.

Proof. For the crown graph with vertex set, mi- nimum covering set of crown graph is. Then

Characteristic polynomial is

.

Characteristic equation is

Minimum covering Randić Spec

Minimum covering Randić energy,

Theorem 2.6 The minimum covering Randić energy, of the complete bipa- rtite graph is equal to.

Proof. For the complete bipartite graph with vertex set , minimum covering set is. Then

Characteristic equation is

Minimum covering Randić Spec

Minimum covering Randić energy,

Definition 2.4 Friendship graph is the graph obtained by taking n copies of the cycle graph with a vertex in common. It is denoted by. Friendship graph con- tains vertices and edges.

Theorem 2.7 The minimum covering Randić energy, of friendship graph

is equal to.

Proof. For a friendship graph with vertex set , minimum covering set is . Then

Characteristic equation is

.

Minimum covering Randić Spec

Minimum covering Randić energy,

2.2. Properties of Minimum Covering Randić Eigenvalues

Theorem 2.8 Let G be a graph with vertex set, edge set E and be a minimum covering set. If are the eigenvalues of minimum covering Randić matrix then (i) (ii) .

Proof. i) We know that the sum of the eigenvalues of is the trace of

.

ii) Similarly the sum of squares of the eigenvalues of is trace of

2.3. Bounds for Minimum Covering Randić Energy

Mclelland’s [8] gave upper and lower bounds for ordinary energy of a graph. Similar bounds for are given in the following theorem.

Theorem 2.9 Let G be a simple graph with n vertices and m edges . If C is the minimum covering set and then

.

Proof.

Canchy Schwarz inequality is

If then

[From theorem 2.8]

Since arithmetic mean is greater than or equal to geometric mean we have

(2.1)

Now consider,

[From (2.1)]

Theorem 2.10 If is the largest minimum covering Randić eigenvalue of , then.

Proof. For any nonzero vector X, we have by [16] ,

where is a unit column matrix.

Just like Koolen and Moulton’s [17] upper bound for energy of a graph, an upper bound for is given in the following theorem.

Theorem 2.11 If G is a graph with n vertices and m edges and then

.

Proof.

Cauchy-Schwartzin equality is

Put then

Let

For decreasing function

Since, we have

Milovanović [18] bounds for minimum covering Randić energy of a graph are given in the following theorem.

Theorem 2.12 Let G be a graph with n vertices and m edges. Let be a non-increasing order of minimum covering Randić eigen- values of and C is minimum covering set then where and denotes the integral part of a real number.

Proof. For real numbers and with and the following inequality is proved in [19] . where and equality holds if and only if and.

If and, then

But and then the above inequality becomes

Theorem 2.13 Let G be a graph with n vertices and m edges. Let be a non-increasing order of minimum covering eigenvalues of then

Proof. Let and R be real numbers satisfying, then the fol- lowing inequality is proved in [20] .

Put and then

The question of when does the graph energy becomes a rational number was answered by Bapat and S. pati in their paper [21] . Similar result for minimum covering Randić energy is obtained in the following theorem.

Theorem 2.14 Let G be a graph with a minimum covering set C. If the minimum covering Randić energy is a rational number, then (mod 2).

Proof. Proof is similar to theorem 3.7 of [15] .

3. Conclusion

It was proved in this paper that the minimum covering Randić energy of a graph G depends on the covering set that we take for consideration. Upper and lower bounds for minimum covering Randić energy are established. A generalized expression for minimum covering Randić energies for star graph, complete graph, thorn graph of com- plete graph, crown graph, complete bipartite graph, cocktail party graph and friendship graphs are also computed.

Acknowledgements

The authors are thankful to anonymous referees for their valuable comments and useful suggestions.

Authors Contributions

Both the authors worked together for the preparation of the manuscript and both of us take the full responsibility for the content of the paper. However second author typed the paper and both of us read and approved the final manuscript.

Conflict of Interests

The authors hereby declares that there are no issues regarding the publication of this paper.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Bozkurt, S.B., Güngör, A.D. and Gutman, I. (2010) Randić Spectral Radius and Randić Energy. Communications in Mathematical and in Computer Chemistry, 64, 239-250.
[2]	Gutman, I. (1978) The Energy of a Graph. Ber. Math-Statist. Sekt. Forschungsz. Graz, 103, 1-22.
[3]	Gutman, I., Li, X. and Zhang, J. (2009) Graph Energy. In: Dehmer, M. and Emmert-Streib, F., Eds., Analysis of Complex Networks. From Biology to Linguistics, Wiley-VCH, Weinheim, 145-174.
[4]	Cvetković, D. and Gutman, I., Eds. (2009) Applications of Graph Spectra. Mathematical Institution, Belgrade.
[5]	Cvetković, D. and Gutman, I., Eds. (2011) Selected Topics on Applications of Graph Spectra. Mathematical Institute Belgrade.
[6]	Gutman, I. (2001) The Energy of a Graph: Old and New Results. In: Betten, A., Kohnert, A., Laue, R. and Wassermann, A., Eds., Algebraic Combinatorics and Applications, Springer, Berlin, 196-211.
[7]	Liu, H.Q., Lu, M. and Tian, F. (2007) Some Upper Bounds for the Energy of Graphs. Journal of Mathematical Chemistry, 41, 45-57. https://doi.org/10.1007/s10910-006-9183-9
[8]	McClelland, B.J. (1971) Properties of the Latent Roots of a Matrix: The Estimation of π - Electron Energies. The Journal of Chemical Physics, 54, 640-643. https://doi.org/10.1063/1.1674889
[9]	Gutman, I. and Polansky, O.E. (1986) Mathematical Concepts in Organic Chemistry. Springer, Berlin. https://doi.org/10.1007/978-3-642-70982-1
[10]	Graovac, A., Gutman, I. and Trinajstić, N. (1977) Topological Approach to the Chemistry of Conjugated Molecules. Springer, Berlin. https://doi.org/10.1007/978-3-642-93069-0
[11]	Randić, M. (1975) On Characterization of Molecular Branching, Journal of the American Chemical Society, 97, 6609-6615. https://doi.org/10.1021/ja00856a001
[12]	Bozkurt, S.B. and Bozkurt, D. (2013) Sharp Upper Bounds for Energy and Randić Energy. Communications in Mathematical and in Computer Chemistry, 70, 669-680.
[13]	Dilek Maden, A. (2015) New Bounds on the Incidence Energy, Randić Energy and Randić Estrada Index. Communications in Mathematical and in Computer Chemistry, 74, 367-387.
[14]	Das, K.Ch., Sorgun, S. and Gutman, I. (2015) On Randić Energy. Communications in Mathematical and in Computer Chemistry, 73, 81-92.
[15]	Adiga, C., Bayad, A., Gutman, I. and Srinivas, S.A. (2012) The Minimum Covering Energy of a Graph. Kragujevac Journal of Science, 34, 39-56.
[16]	Bapat, R.B. (2011) Graphs and Matrices. Hindustan Book Agency, Gurgaon, No.32.
[17]	Koolen, J.H. and Moulton, V. (2001) Maximal Energy Graphs. Advances in Applied Mathematics, 26, 47-52. https://doi.org/10.1006/aama.2000.0705
[18]	Milovanović, I.Z., Milovanović, E.I. and Zakić, A. (2014) A Short Note on Graph Energy. MATCH Communications in Mathematical and in Computer Chemistry, 72, 179-182.
[19]	Biernacki, M., Pidek, H. and Ryll-Nadzewski, C. (1950) Sur une inequalite entre des inegrales defnies. Annales Universitatis Mariae Curie-Sklodowska Sectio A, 4, 1-4.
[20]	Diaz, J.B. and Matcalf, F.T. (1963) Stronger Forms of a Class Inequalities of G. Polja-G. Szego and L. V. Kantorovich. Bulletin of the American Mathematical Society, 69, 415-418. https://doi.org/10.1090/S0002-9904-1963-10953-2
[21]	Bapat, R.B. and Pati, S. (2011) Energy of a Graph Is Never an Odd Integer. Bulletin of Kerala Mathematics Association, 1, 129-132.