Pure and Applied Mathematics Journal
Volume 5, Issue 5, October 2016, Pages: 165-173

Pentacyclic Harmonic Graph

Ahmad Salehi Zarrin Ghabaei, Shahroud Azami

Department of Mathematics, Parand Branch, Islamic Azad University, Parand, Iran

Email address:

(A. S. Z. Ghabaei)
(S. Azami)

To cite this article:

Ahmad Salehi Zarrin Ghabaei, Shahroud Azami. Pentacyclic Harmonic Graph. Pure and Applied Mathematics Journal. Vol. 5, No. 5, 2016, pp. 165-173. doi: 10.11648/j.pamj.20160505.15

Received: August 28, 2016; Accepted: September 8, 2016; Published: October 11, 2016


Abstract: Let  be a graph on n vertices  and let  be the degree of vertex  A graph  is defined to be harmonic if  is an eigenvector of the -adjacency matrix of  We now show that there are 4 regular and 45 non-regular connected pentacyclic harmonic graphs and determine their structure. In the end we conclude that all of c-cyclic harmonic graphs for  are planar graphs.

Keywords: Harmonic Graph, Eigenvalue, Spectra


1. Introduction

Let  be a graph with  vertices  and edges. We say that  is c-cyclic, whenever which  is the number components of  In [1] B. Borovicanin and et al, studied the c-cycle graphs for  All harmonic trees were constructed in [8] and the number of walks counted on some harmonic graph in [4, 5]. In [9, 10, 11] founded some result on harmonic graphs.

In this paper we study the c-cycle graphs for . If the graph  is connected and then  is a tree.

The following elementary properties of harmonic graphs obtain of the spectra properties of graphs [2, 3, 6, 7]. Let  be the degree of vertex  for , that is the number of the first neighbors of  Vertex of degree k is called a k-vertex. Vertex of degree zero is called pendent. The column-vector  is denoted by . The number of k-vertex denoted by  and we have

(1)

(2)

Definition 1. The adjacency matrix  is the  matrix for which  if  and otherwise. Eigenvalues and eigenvectors of matrix  is called eigenvalues and eigenvectors of graph.

Definition 2. A graph  is said to be harmonic if there exists a constant , such that

(3)

In other words

(4)

Thus, graph is harmonic if and only if  is one of its eigenvectors, theses graphs are called -harmonic. Equation (3) result that  is a rational number and equation (4) implies that  is not proper fraction, they follows that  must be an integer.

Example 1. A -regular graph is a -harmonic graph.

By summing the expressions (3) over all  we have

(5)

equivalently

(6)

2. Some Auxiliary Results

We have the follow results of [1].

Lemma 1.

i.           Let H be a graph obtained from G by adding to it an arbitrary number of isolated vertices, then H is harmonic if and only if G is harmonic.

ii.         Any graph without isolated vertices is -harmonic if and only if all its components are -harmonic.

iii.        Let G be a connected -harmonic graph. Then  is greatest eigenvalue of G and its multiplicity is one. Also if  then  and equality occurs if and only if .

From Lemma 2.1., it is enough to restrict our considerations to connected non-regular graphs. In [8], shown that for any positive integer  there is a unique connected -harmonic that is a tree and denoted by .  has  vertices, of which one vertices is a -vertex, vertices are -vertices and  vertices are pendant. Also in [1], shown that the following lemmas:

Lemma 2.

a          In a -harmonic graph 1-vertex is adjacent to a vertex of degree .

b          If a -harmonic graph not regular, then it has a vertex of degree greater than .

c           In a harmonic graph with , no 1-vertex is attached to any vertex of greatest degree.

Lemma 3.

The tree  is the unique connected non-regular 2-harmonic graph.

Lemma 4.

If  is a vertex of a -harmonic graph then . If then  belongs to a tree , otherwise .

Lemma 5: For the -harmonic tree, . For any other connected -harmonic graph, .

Lemma 6.

If  be a connected c-cyclic -harmonic graph with , then .

Lemma 7.

Let  be a vertex of a -harmonic graph such that , and let  be a vertex adjacent to , then .

After then, we suppose that c-cyclic graphs are connected, that is  therefore . By combining the equalities (1) and (2) we get

(7)

3. The Main Result

Theorem 1.

There are exactly 45 non-regular connected pentacyclic harmonic graphs, depicted in Figures 1- 17.

Proof:

Because of Lemma 6, if  then  cannot be greater than 4. Since , therefore, , on the other hand, Lemmas 2 and 5, result that  cannot equal to1 and 2, hence  or . At the first, suppose that .

By the Lemma 2.4 if  is the maximal degree in a pentacyclic harmonic graph, then  and in case by Lemma 4 we have . From Lemma 2 we the conclude that only the following 11 cases need to be examined:

Case 1:

Case 2:

Case 3:

Case 4:

Case 5:

Case 6:

Case 7:

Case 8:

Case 9:

Case 10:

Case 11:

Case 1: Lemma 5 implies that . By means of relation (7), for , we have

(8)

from which

(9)

and we can conclude that

(10)

from equation (1.6) we get

(11)

According to Lemma 7, the 5 and 6-vertices are adjacent only to 3-vertices. Since (3) the two neighbors of every 3-vertex, adjacent to a 6-vertex, must be a 1 and 2-vertex. Therefore , , and consequently, . In what follows we distinguish between 12 subcases:

Subcase 1:

(12)

In this subcase, we have, , , , , , . Each of the three 2-vertices must be adjacent to two 3-vertices, and exacts of 4, 3-vertices remains. Therefore there cannot exist a 3-harmonic satisfies the condition (12).

Subcase 2:

(13)

The 4 and 6-vertices are adjacent only to 3-vertices and therefore the number of 3-vertices is greater than or equal to 10. Because of  we now have . Then, in this subcase we get

(14)

the neighbors 3-vertex adjacent to 4-vertex has a 2-vertex, a 3-vertex, so we need at least 5, 2-vertices. This subcase also impossible.

Subcase 3:

(15)

Similar arguments subcase 2, we have

(16)

this graph is nonconnected, then this subcase is impossible.

Subcase 4:

(17)

The 5 and 6-vertices are adjacent only to 3-vertices and therefore the number of 3-vertices is greater than or equal to 11. Because of  we now have . Then, in this subcase we get

Table 1. Cases of .

 

(a) 10 4 11 0 1 1
(b) 11 3 12 0 1 1

the only case (a) can occurs and its graph is as follows.

Figure 1. First member of a family of 3-harmonic graphs which c=5 and .

Subcase 5:

(18)

Since 3-vertices adjacent to 4-vertex, 5-vertex, 6-vertex, are distinct, so we need at least 15, 3-vertices, then . It result that  that impossible.

Subcase 6:

(19)

Similar arguments Subcase 1.5 this subcase is impossible.

Subcase 7:

(20)

Since 3-vertices adjacent to 6-vertices are distinct, so we need at least 12, 3-vertices and 6, 2-vertices, then . It result that  that impossible.

Subcase 8:

(21)

In this subcase we have  then  and  that impossible.

Subcase 9:

(22)

In this subcase we have  then  and  that impossible.

Subcase 10:

(23)

In this subcase we have  therefore  and  that this is a contradiction.

Subcase 11:

(24)

In this subcase we have  thus  and  that this cannot happen.

Subcase 12:

(25)

In this subcase we get  hence  and  that impossible.

Case 2:

Lemma 5 follows that . Equations (6) and (7) now became

(26)

and

(27)

We have following subcases:

Subcase 13:

(28)

By the Lemma 7, every 5-vertex is adjacent only with 3-vertices. Therefore  and , then we have

Table 2. Cases of .

  n1 n2 n3 n4 n5
(a) 8 2 10 0 2
(b) 9 1 11 0 2
(c) 10 0 12 0 2

Case (b) does not hold, but for case (a) we have 3 harmonic graphs as follow:

Figure 2. First members of a family of 3-harmonic graphs which c=5 and .

and for case (c) we have 8 harmonic graphs as follow:

Figure 3. Second members of a family of 3-harmonic graphs which c=5 and .

Subcase 14:

(29)

In this subcase we have then and  that impossible.

Subcase 15:

(30)

Since  then this subcase is impossible.

Subcase 16:

(31)

In this subcase we have then we have

Table 3. Cases of .

  n1 n2 n3 n4 n5
(a) 0 5 5 0 1
(b) 1 4 6 0 1
(c) 2 3 7 0 1
(d) 3 2 8 0 1
(e) 4 1 9 0 1
(f) 5 0 10 0 1

cases (b), (c) and (e) do not hold, but for case (a) we have 2 harmonic graphs as follow:

Figure 4. Third members of a family of 3-harmonic graphs which c=5 and .

for case (d) we have 1 harmonic graphs as follow:

Figure 5. Fourth members of a family of 3-harmonic graphs which c=5 and .

for case (f) we have 3 harmonic graphs as follow:

Figure 6. Fifth members of a family of 3-harmonic graphs which c=5 and .

Subcase 17:

(32)

In this subcase we have  then  and

Table 4. Cases of .

 

(a) 6 1 9 1 1
(b) 7 0 10 1 1

since the neighbors 3-vertex adjacent to 4-vertex has a 2-vertex, a 3-vertex, so we need at least 2, 2-vertices, then this subcase is impossible.

Subcase 18:

(33)

In this subcase we have  hence  and

Table 5. Cases of .

  n1 n2 n3 n4 n5
(a) 8 1 9 2 1
(b) 9 0 10 2 1

since some the neighbors 3-vertex adjacent to 5-vertex has a 2-vertex, a 3-vertex, so we need at least 2, 2-vertices, then this subcase is impossible.

Case 3:

Lemma 5 follows that . Equations (6) and (7) now became

(34)

and

(35)

 results that  and the other hand , then we have following subcases:

Subcase 19:

(36)

Equivalently

Table 6. Cases of .

  n1 n2 n3 n4
(a) 1 1 7 1
(b) 2 0 8 1
(c) 0 2 6 1

since the neighbors 3-vertex adjacent to 4-vertex has a 2-vertex, a 3-vertex, so we need at least 2, 2-vertices, then subcases (a) and (b) are impossible, but for case (c) we have 2 harmonic graphs as follow:

Figure7. First members of a family of 3-harmonic graphs which c=5 and .

Subcase 20:

(37)

equivalently

Table 7. Cases of .

  n1 n2 n3 n4
(a) 0 4 4 2
(b) 1 3 5 2
(c) 2 2 6 2
(d) 3 1 7 2
(e) 4 0 8 2

for case (a) we have 3 harmonic graphs as follow:

Figure 8. Second members of a family of 3-harmonic graphs which c=5 and .

In subcase (b) we need at least 6, 3-vertices, then this subcase is impossible, also subcases (d) and (e) are impossible, but for case (c) we have 3 harmonic graphs as follow:

Figure 9. Third members of a family of 3-harmonic graphs which c=5 and .

Subcase 21:

(38)

If any two 4-vertices of three 4-vertices be adjacent, then , thus this manner cannot occurs. If just a 4-vertex adjacent with the other 4-vertices, then we have 2 harmonic graphs as follow:

Figure 10. Fourth members of a family of 3-harmonic graphs which c=5 and .

if the only two 4-vertices of three 4-vertices be adjacent, then we have 2 harmonic graphs as follow:

Figure 11. Fifth members of a family of 3-harmonic graphs which c=5 and .

Subcase 22:

(39)

equivalently

Table 8. Cases of .

  n1 n2 n3 n4
(a) 0 8 0 4
(b) 1 7 1 4
(c ) 2 6 2 4
(d) 3 5 3 4
(e) 4 4 4 4
(f) 5 3 5 4
(g) 6 2 6 4
(h) 7 1 7 4
(k) 8 0 8 4

In above subcases we need to the even number of 3-vertices, then these subcases (b), (d), (e) and (h) are impossible. For case (a) we have 4 harmonic graphs as follow:

Figure 12. Sixth members of a family of 3-harmonic graphs which c=5 and .

for case (c) we have 3 harmonic graphs as follow:

Figure 13. Seventh members of a family of 3-harmonic graphs which c=5 and .

for case (e) we have 2 harmonic graphs as follow:

Figure 14. Eighth members of a family of 3-harmonic graphs which c=5 and .

for case (g) we have 2 harmonic graphs as follow:

Figure 15. Ninth members of a family of 3-harmonic graphs which c=5 and .

and also for case (k) we have 3 harmonic graphs as follow:

Figure 16. Tenth members of a family of 3-harmonic graphs which c=5 and .

Case 4:

Lemma 5 follows that . Equations (6) and (7) now became

(40)

and

(41)

Since  and  then this case is impossible.

Case 5:

Lemma 5 follows that . Equations (6) and (7) now became

(42)

and

(43)

Because of  and  this cannot happen.

Case 6:

Lemma 5 follows that . Equations (6) and (7) now became

(44)

and

(45)

Since  and  then (45) implies that

(46)

and (45) results that . Since vertices adjacent to 10-vertex are 4-vertex then  and . The equation  leads to . This harmonic graph as follow:

Figure 17. First member of a family of 4-harmonic graphs which c=5 and .

Case 7:

From Lemma 5 we get . Equations (6) and (7) imply that

(47)

and

(48)

Because of  and  the relation (48) implies that

(49)

or

(50)

and (47) results that . Since vertices adjacent to 9-vertex are 4-vertex then  and . The equation  results that this case is impossible.

Case 8:

Lemma 5 leads to . From equations (6) and (7) we get

(51)

and

(52)

Since  and  then (52) implies that

(53)

and (51) implies that . Since vertices adjacent to 8-vertex are 4-vertex so  and . The equation  results that this case is impossible.

Case 9:

From Lemma 5 we have . Equations (6) and (7) lead to

(54)

and

(55)

Since  and  then (55) implies that

(56)

and (54) results that . If  then vertices adjacent to 7-vertex are 4-vertex then  and . The equation  results that this case is impossible. Also, if  then  and , then since some of vertices adjacent to 7-vertex are 4-vertex then  and . The equation  results that this case is impossible.

Case 10:

Lemma 5 follows that . Equations (6) and (7) now became

(57)

and

(58)

We have following subcases:

Subcase 23:

(59)

If  then ,  therefore this manner not occurs. If then  and . On the other hand  thus  that this contradiction with . Hence this manner also cannot occurs.

Subcase 24:

(60)

If  then ,  therefore this manner is impossible. If then  and . Also,  thus  that this contradiction with . Therefore this case also cannot occurs.

Subcase 25:

(61)

In this subcases ,  then this case is impossible.

Subcase 26:

(62)

In this subcases ,  then this case cannot happen.

Subcase 27:

(63)

In this subcases , . Since vertices adjacent to 6-vertex are 4-vertex then  and . So this contradiction with . Then this case is impossible.

Subcase 28:

(64)

since some vertices adjacent to 6-vertex are 4-vertex then  and , . That this contradiction with , then this case is impossible.

Case 11:

Lemma 5 follows that . Equations (6) and (7) now became

(65)

and

(66)

 then we have following subcases:

Subcase 29:

(67)

Since vertices adjacent to 5-vertex are 4-vertex then  and  that this contradiction with . Hence this case is impossible.

Subcase 30:

(68)

Since  and , hence this case cannot happen.

Subcase 31:

(69)

Since some vertices adjacent to 5-vertex are 4-vertex then  and  that this contradiction with . Therefore this case is impossible.

Subcase 32:

(70)

Some vertices adjacent to 5-vertex are 4-vertex then  and  that this contradiction with . Thus this case is impossible.

Subcase 33:

(71)

Since some vertices adjacent to 5-vertex are 4-vertex then  and  that this contradiction with . Hence this case is impossible.

Definition 3:

A graph is planar if it can be drawn in a plane without graph edges crossing.

Corollary 1:

All of c-cyclic nonregular harmonic graphs for  are planar graphs.

4. Regular Harmonic Graphs

If a pentacyclic -harmonic graph be regular then we have  and , therefore we have the only . In this case we have 4, 3-harmonic graphs as follow:

Figure 18. Connected regular pentacyclic harmonic graphs.

5. Conclusions

Let # r(c) and #nr(c) be denote the number of connected c-cyclic regular and nonregular harmonic graphs, respectively, for a fixed value c. According to fined results, the number of harmonic graphs as follows.

Table 9. The number of harmonic graphs.

c # r(c) #nr(c) Remark
0 1

1

0

2 0 0  
3 1 4

4 2 18

5 4 45

finite finite  

References

  1. Borovicanin B., Grunewald S., Gutman I., Petrovic M. 2003. Harmonic graphs with small number of cycles, Discrete Mathematics 265, 31-44.
  2. Cvetkovi'c D., Doob M., Sachs H. 1995. Spectra of Graphs: Theory and Applications (3rd ed.), Johann Ambrosius Barth, Heidelberg.
  3. Cvetkovi'c D., Rowlinson P., Simi'c S. 1997. Eigenspaces of Graphs, Cambridge University Press, Cambridge.
  4. Dress A., Gutman I. 2003. Asymptotic results regarding the number of walks in a graph, Appl. Math. Lett., 16(3), 389-393.
  5. Dress A., Gutman I. 2003. On the number of walks in a graph, Appl. Math. Lett. 16(5), 797-801.
  6. Favaron O., Mah'eo M., Sacl'e J.F., 1993. Some eigenvalue properties in graphs (conjectures of GraLti—II), Discrete Math. 111, 197–220.
  7. Godsil C., Royle G. 2001. Algebraic Graph Theory, Springer-Verlag, New York.
  8. Grunewald S. 2002. Harmonic tree, App. Math. Lett. 15, 1001-1004.
  9. Petrovi´c M., Borovi´canin B., Radosavljevi´c Z. 2006. The integral 3-harmonic graphs, Linear Algebra and its Applications 416, 298–312.
  10. Mahmoodi A. 2013. Some Results on Harmonic Graphs, Gen. Math. Notes, 19(1), 53-59.
  11. Salehi Zarrin Ghabaei A., Azami S. 2014. Some properties of harmonic graphs,Advances in Environmental Biology, 8(11), 597-605.

Article Tools
  Abstract
  PDF(633K)
Follow on us
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931