www

International Scholarly Research Network ISRN Discrete Mathematics Volume 2011, Article ID 262183, 7 pages doi:10.5402/2...

0 downloads 14 Views 480KB Size
International Scholarly Research Network ISRN Discrete Mathematics Volume 2011, Article ID 262183, 7 pages doi:10.5402/2011/262183

Research Article On the Randic´ Index of Corona Product Graphs ´ Ismael G. Yero and Juan A. Rodr´ıguez-Velazquez Departamento d’Enginyeria Inform`atica i Matem`atiques, Universitat Rovira i Virgili, Avinguda Pa¨ısos Catalans 26, 43007 Tarragona, Spain Correspondence should be addressed to Ismael G. Yero, [email protected] Received 24 July 2011; Accepted 20 September 2011 Academic Editor: X. Yong Copyright q 2011 I. G. Yero and J. A. Rodr´ıguez-Vel´azquez. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Let G be a graph with vertex set V  v1 , v2 , . . . , vn . Let δvi  be the degree of the vertex vi ∈ V . If the vertices vi1 , vi2 , . . . , vih1 form a path of length h≥ 1 in the graph G, then the hth order Randi´c index Rh of G is defined as the sum of the terms 1/ δvi1 δvi2  · · · δvih1  over all paths of length h contained as subgraphs in G. Lower and upper bounds for Rh , in terms of the vertex degree sequence of its factors, are obtained for corona product graphs. Moreover, closed formulas are obtained when the factors are regular graphs.

1. Introduction In this work we consider simple graphs G  V, E with n vertices and m edges. Let V  v1 , v2 , . . . , vn  be the vertex set of G. For every vertex vi ∈ V , δvi  represents the degree of the vertex vi in G. The maximum and minimum degree of the vertices of G will be denoted by Δ and δ, respectively. The Randi´c index R1 G of a graph G was introduced in 1975 1 and defined as

R1 G 



1   . vi vj ∈E δvi δ vj

1.1

This graph invariant, sometimes referred to as connectivity index, has been successfully related to a variety of physical, chemical, and pharmacological properties of organic molecules, and it has became into one of the most popular molecular-structure descriptors. After the publication of the first paper 1, mathematical properties of R1 were extensively studied, see 2–6 and the references cited therein.

2

ISRN Discrete Mathematics

The higher-order Randi´c indices are also of interest in chemical graph theory. For h ≥ 1, the hth order Randi´c index Rh G of a graph G is defined as 

Rh G 



vi1 vi2 ···vih1 ∈Ph G

1 δvi1 δvi2  · · · δvih1 

,

1.2

where Ph G denotes the set of paths of length h contained as subgraphs in G. Of the higherorder Randi´c indices the most frequently applied is R2 7–10. Estimations of the higher-order Randi´c index of regular graphs and semiregular bipartite graphs are given in 10. In this paper we are interested in studying the higher-order Randi´c index, Rh , for corona product graphs. Roughly speaking, we study the cases h  1, h  2 for arbitrary graphs and the case h ≥ 3 when the second factor of the corona product is an empty graph. As an example of a chemical compound whose graph is obtained as a corona product graph we consider the Cycloalkanes with a single ring, whose chemical formula is Ck H2k , and whose molecular graph can be expressed as Ck N2 , where Ck is the cycle graph of order k and N2 is the empty graph of order two. We recall that, given two graphs G and H of order n1 and n2 , respectively, the corona product G  H is defined as the graph obtained from G and H by taking one copy of G and n1 copies of H and then joining by an edge each vertex of the ith copy of H with the ith vertex of G.

2. Estimating Rh for Corona Graphs Theorem 2.1. For i ∈ {1, 2}, let Gi be a graph of minimum degree δi , maximum degree Δi , order ni and size mi . Then, R1 G1  G2  ≤

n1 n2 n1 m2 m1   , δ1  n2 δ2  1 δ1  n2 δ2  1

n1 n2 n1 m2 m1 R1 G1  G2  ≥   . Δ1  n2 Δ2  1 Δ1  n2 Δ2  1

2.1

Proof. Let Gi  Vi , Ei , i ∈ {1, 2}, and let G1  G2  V, E. We have R1 G1  G2  





xy∈E

1

   Q1  Q2  Q3 , δxδ y

2.2

where Q1 





ab∈E1

Q2  Q3 

1 δa  n2 δb  n2 



m1 , Δ1  n2



1 n1 m2 , ≥  Δ 21 δu  1δv  1 uv∈E2  a∈V1 , u∈V2



n1 n2 ≥ . Δ1  n2 Δ2  1 δa  n2 δu  1 1

Thus, the lower bound follows. Analogously we deduce the upper bound.

2.3

ISRN Discrete Mathematics

3

Corollary 2.2. For i ∈ {1, 2}, let Gi be a δi -regular graph of order ni . Then, R1 G1  G2  

n1 n2 n1 n2 δ2 n1 δ1 .   2δ1  n2  2δ2  1 δ1  n2 δ2  1

2.4

Theorem 2.3. For i ∈ {1, 2}, let Gi be a graph of minimum degree δi , maximum degree Δi , order ni , and size mi . Then,   n2 n2 − 1 n1 R2 G1  G2  ≤  2m2  2 δ2  1 δ1  n2 ⎛ ⎞  δvi δvi  − 1 1 ⎝ 2n2 m1 ⎠     δ1  n2 δ2  1 δv ≥2 2 δvi   n2 i



 δui δui  − 1 1 ,  2δ2  1 δu ≥2 δui   1 i

  n2 n2 − 1 n1  2m2 R2 G1  G2  ≥  2 Δ2  1 Δ1  n2 ⎛ ⎞  δvi δvi  − 1 1 ⎝ 2n2 m1 ⎠     Δ1  n2 Δ2  1 δv ≥2 2 δvi   n2

2.5

i



 δui δui  − 1 .  2Δ2  1 δu ≥2 δui   1 i 1

Proof. Let V1  {v1 , v2 , . . . , vn1 } and V2  {u1 , u2 , . . . , un2 } be the set of vertices of G1 and G2 , respectively. Given a vertex v ∈ Vi , we denote by NGi v the set of neighbors that v has in Gi . The paths of length two in G1  G2 are obtained as follows: i paths ui vj uk , i /  k, where ui , uk ∈ V2 and vj ∈ V1 ,  k, where ui ∈ V2 and vj vk ∈ V1 , ii paths ui vj vk , j /  k, where vi ∈ V1 and uj , uk ∈ V2 , iii paths vi uj uk , j / iv paths of length two belonging to G1 , v paths of length two belonging to the n1 copies of G2 .

So, we have R2 G1  G2   5i1 Qi , where Q1 







1      vj ∈V1 ; ui ,uk ∈V2 δui   1 δ vj  n2 δuk   1 n1 

n n2 2 −1  1 1 ·     j1 δ vj  n2 i1 li1 δui   1δul   1

n1 n2 n2 − 1  2Δ2  1 Δ1  n2

2.6

4

ISRN Discrete Mathematics

corresponds to the paths type i, 

Q2 



ui ∈V2 ; vj ,vk ∈V1



n2 



i1



1     δui   1 δ vj  n2 δvk   n2 

1

n1 



1     δui   1 j1 vl ∈NG1 vj  δ vj  n2 δvl   n2  ·

2.7

2m1 n2  Δ1  n2  Δ2  1

corresponds to the paths type ii, 

Q3 



vi ∈V1 ;uj ,uk ∈V2





1     δvi   n2  δ uj  1 δuk   1

n1 

n2   1 1 ·      δvi   n2 j1 ul ∈NG2 uj  i1 δ uj  1 δul   1

2.8

2n1 m2  Δ2  1 Δ1  n2

corresponds to the paths type iii, 

Q4 



vi vj vk ∈PG1 

1     δvi   n2  δ vj  n2 δvk   n2 

 δvi δvi  − 1 1 ≥  2Δ1  n2  δv ≥2 δvi   n2

2.9

i

corresponds to the paths type iv, and

Q5 

 ui uj uk ∈PG2 



1     δui   1 δ uj  1 δuk   1

 δui δui  − 1 ≥  2Δ2  1 δu ≥2 δui   1 i 1

2.10

corresponds to the paths type v. Thus, the lower bound follows. The upper bound is obtained by analogy.

ISRN Discrete Mathematics

5

Corollary 2.4. For i ∈ {1, 2}, let Gi be a δi -regular graph of order ni . Then, R2 G1  G2  

  n2 − 1 n1 n2  δ2  2 δ2  1 δ1  n2   n2 δ2 δ2 − 1 δ1 − 1 n1 δ1 2n2   .    2δ1  n2  δ2  1 δ1  n2 2δ2  1 δ2  1

2.11

The girth of a graph is the size of its smallest cycle. For instance, the molecular graphs of benzenoid hydrocarbons have girth 6. The molecular graphs of biphenylene and azulene have girth 4 and 5, respectively 11. The following result, and its proof, was implicitly obtained in the proof of Theorem 1 of 10. By completeness, here we present it as a separate result. Lemma 2.5. Let G  V, E be a graph with girth gG. If δ ≥ 2 and gG > h, then the number of paths of length h in G is bounded by δ − 1h−2  Δ − 1h−2  δuδu − 1 ≤ |Ph G| ≤ δuδu − 1. 2 2 u∈V u∈V

2.12

Proof. Since δ ≥ 2, for every v ∈ V , the number of paths of length 2 in G of the form vi vvj is δvδv − 1/2. Therefore, the result follows for h  2. Suppose now that h ≥ 3. Given a vertex u ∈ V , let Ph u be the set of paths of length h whose second vertex is u, that is, paths of the form u1 uu2 · · · uh . We denote by Nv the set of neighbors of an arbitrary vertex v ∈ V . Note that the degree of v is δv  |Nv|. If δ ≥ 2, then for every v ∈ V and w ∈ Nv we have Nw \ {v}  / ∅. So, for every u ∈ V , there exists a vertex sequence u1 uu2 · · · uh such that u1 , u2 ∈ Nu, u3 ∈ Nu2  \ {u}, u4 ∈ Nu3  \ {u2 }, . . . , and uh ∈ Nuh−1  \ {uh−2 }. If gG > h, then the sequence u1 uu2 · · · uh is a path. Conversely, every path of length h whose second vertex is u can be constructed as above. Hence, the number of paths of length h whose second vertex is u is bounded by ⎧ ⎨

⎫ h−1     ⎬ δuδu − 1 min δ uj − 1 |Ph u| ≥ ⎭ u1 uu2 ···uh ∈Ph u⎩ j2 ≥ δuδu − 1δ − 1h−2 , ⎧ ⎫ h−1 ⎨     ⎬ δuδu − 1 max δ uj − 1 |Ph u| ≤ ⎭ u1 uu2 ···uh ∈Ph u⎩ j2 ≤ δuδu − 1Δ − 1h−2 . Thus, the result follows. Now Nk denotes the empty graph of order k.

2.13

6

ISRN Discrete Mathematics

Theorem 2.6. Let G  V, E be a graph with girth gG, minimum degree δ, and maximum degree Δ. If δ ≥ 2 and gG > h ≥ 3, then 

 Δ−1 Δ − 1h−3  δuδu − 1, k √ 2 δk δ  kh/2 u∈V   δ−1 δ − 1h−3  Rh G  Nk  ≥ k δuδu − 1. √ 2 Δk Δ  kh/2 u∈V Rh G  Nk  ≤

2.14

Proof. The paths of length h in G contribute to Rh G  Nk  in  vi1 vi2 ···vih1 ∈Ph G

 h1

1

l1 δvil   k

.

2.15

Moreover, each path of length h − 1 in G leads to 2k paths of length h in G  Nk ; thus, the paths of length h − 1 in G contribute to Rh G  Nk  in  vi1 vi2 ···vih ∈Ph−1 G

2k

 h

l1 δvil 

 k

.

2.16

Hence, Rh G  Nk  

 vi1 vi2 ···vih1 ∈Ph G

|Ph G|

≤ δ  kh1

 h1 l1

1 δvil   k



 vi1 vi2 ···vih ∈Ph−1 G



|Ph−1 G|  2k  . δ  kh

2k

h l1 δvil 

 k

2.17

By Lemma 2.5 we obtain the upper bound and the lower bound is obtained by analogy. Corollary 2.7. Let G  V, E be a δ-regular graph of order n and girth gG. If δ ≥ 2 and gG > h ≥ 3, then  Rh G  Nk  

 δ−1 nδδ − 1h−2 . k √ 2 δk δ  kh/2

2.18

Acknowledgment This work was partly supported by the Spanish Government through projects TSI2007-65406C03-01 “E-AEGIS” and CONSOLIDER INGENIO 2010 CSD2007-00004 “ARES.”

ISRN Discrete Mathematics

7

References 1 M. Randi´c, “On characterization of molecular branching,” Journal of the American Chemical Society, vol. 97, no. 23, pp. 6609–6615, 1975. 2 Y. Hu, X. Li, Y. Shi, T. Xu, and I. Gutman, “On molecular graphs with smallest and greatest zerothorder general Randi´c index,” Match, vol. 54, no. 2, pp. 425–434, 2005. 3 H. Li and M. Lu, “The m-connectivity index of graphs,” Match, vol. 54, no. 2, pp. 417–423, 2005. 4 X. Li and Y. Shi, “A survey on the Randi´c index,” Match, vol. 59, no. 1, pp. 127–156, 2008. 5 B. Liu and I. Gutman, “On general Randi´c indices,” Match, vol. 58, no. 1, pp. 147–154, 2007. 6 J. A. Rodr´ıguez and J. M. Sigarreta, “On the Randi´c index and conditional parameters of a graph,” Match, vol. 54, no. 2, pp. 403–416, 2005. 7 O. Araujo and J. A. De La Pena, ˜ “The connectivity index of a weighted graph,” Linear Algebra and Its Applications, vol. 283, no. 1–3, pp. 171–177, 1998. 8 X. Li and I. Gutman, Thathematical Aspects of Randi´c-Type Molecular Structure Descriptors, Faculty of Science, University of Kragujevac, 2006. 9 J. A. Rodr´ıguez, “A spectral approach to the Randi´c index,” Linear Algebra and Its Applications, vol. 400, pp. 339–344, 2005. 10 I. G. Yero, J. A. Rodr´ıguez-Vel´azquez, and I. Gutman, “Estimating the higher-order Randi´c index,” Chemical Physics Letters, vol. 489, pp. 118–120, 2010. 11 I. Gutman and O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer, Berlin, Germany, 1986.