Pentacyclic Harmonic Graph
Ahmad Salehi Zarrin Ghabaei, Shahroud Azami
Department of Mathematics, Parand Branch, Islamic Azad University, Parand, Iran
Email address:
To cite this article:
Ahmad Salehi Zarrin Ghabaei, Shahroud Azami. Pentacyclic Harmonic Graph. Pure and Applied Mathematics Journal. Vol. 5, No. 5, 2016, pp. 165173. 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 nonregular connected pentacyclic harmonic graphs and determine their structure. In the end we conclude that all of ccyclic 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 ccyclic, whenever which is the number components of In [1] B. Borovicanin and et al, studied the ccycle 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 ccycle 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 kvertex. Vertex of degree zero is called pendent. The columnvector is denoted by . The number of kvertex 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 nonregular 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 1vertex 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 1vertex is attached to any vertex of greatest degree.
Lemma 3.
The tree is the unique connected nonregular 2harmonic 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 ccyclic 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 ccyclic 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 nonregular 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 6vertices are adjacent only to 3vertices. Since (3) the two neighbors of every 3vertex, adjacent to a 6vertex, must be a 1 and 2vertex. Therefore , , and consequently, . In what follows we distinguish between 12 subcases:
Subcase 1:
(12)
In this subcase, we have, , , , , , . Each of the three 2vertices must be adjacent to two 3vertices, and exacts of 4, 3vertices remains. Therefore there cannot exist a 3harmonic satisfies the condition (12).
Subcase 2:
(13)
The 4 and 6vertices are adjacent only to 3vertices and therefore the number of 3vertices is greater than or equal to 10. Because of we now have . Then, in this subcase we get
(14)
the neighbors 3vertex adjacent to 4vertex has a 2vertex, a 3vertex, so we need at least 5, 2vertices. 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 6vertices are adjacent only to 3vertices and therefore the number of 3vertices 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 3harmonic graphs which c=5 and .
Subcase 5:
(18)
Since 3vertices adjacent to 4vertex, 5vertex, 6vertex, are distinct, so we need at least 15, 3vertices, then . It result that that impossible.
Subcase 6:
(19)
Similar arguments Subcase 1.5 this subcase is impossible.
Subcase 7:
(20)
Since 3vertices adjacent to 6vertices are distinct, so we need at least 12, 3vertices and 6, 2vertices, 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 5vertex is adjacent only with 3vertices. Therefore and , then we have
Table 2. Cases of .
n_{1}  n_{2}  n_{3}  n_{4}  n_{5}  
(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 3harmonic graphs which c=5 and .
and for case (c) we have 8 harmonic graphs as follow:
Figure 3. Second members of a family of 3harmonic 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 .
n_{1}  n_{2}  n_{3}  n_{4}  n_{5}  
(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 3harmonic graphs which c=5 and .
for case (d) we have 1 harmonic graphs as follow:
Figure 5. Fourth members of a family of 3harmonic graphs which c=5 and .
for case (f) we have 3 harmonic graphs as follow:
Figure 6. Fifth members of a family of 3harmonic 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 3vertex adjacent to 4vertex has a 2vertex, a 3vertex, so we need at least 2, 2vertices, then this subcase is impossible.
Subcase 18:
(33)
In this subcase we have hence and
Table 5. Cases of .
n_{1}  n_{2}  n_{3}  n_{4}  n_{5}  
(a)  8  1  9  2  1 
(b)  9  0  10  2  1 
since some the neighbors 3vertex adjacent to 5vertex has a 2vertex, a 3vertex, so we need at least 2, 2vertices, 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 .
n_{1}  n_{2}  n_{3}  n_{4}  
(a)  1  1  7  1 
(b)  2  0  8  1 
(c)  0  2  6  1 
since the neighbors 3vertex adjacent to 4vertex has a 2vertex, a 3vertex, so we need at least 2, 2vertices, 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 3harmonic graphs which c=5 and .
Subcase 20:
(37)
equivalently
Table 7. Cases of .
n_{1}  n_{2}  n_{3}  n_{4}  
(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 3harmonic graphs which c=5 and .
In subcase (b) we need at least 6, 3vertices, 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 3harmonic graphs which c=5 and .
Subcase 21:
(38)
If any two 4vertices of three 4vertices be adjacent, then , thus this manner cannot occurs. If just a 4vertex adjacent with the other 4vertices, then we have 2 harmonic graphs as follow:
Figure 10. Fourth members of a family of 3harmonic graphs which c=5 and .
if the only two 4vertices of three 4vertices be adjacent, then we have 2 harmonic graphs as follow:
Figure 11. Fifth members of a family of 3harmonic graphs which c=5 and .
Subcase 22:
(39)
equivalently
Table 8. Cases of .
n_{1}  n_{2}  n_{3}  n_{4}  
(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 3vertices, 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 3harmonic graphs which c=5 and .
for case (c) we have 3 harmonic graphs as follow:
Figure 13. Seventh members of a family of 3harmonic graphs which c=5 and .
for case (e) we have 2 harmonic graphs as follow:
Figure 14. Eighth members of a family of 3harmonic graphs which c=5 and .
for case (g) we have 2 harmonic graphs as follow:
Figure 15. Ninth members of a family of 3harmonic 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 3harmonic 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 10vertex are 4vertex then and . The equation leads to . This harmonic graph as follow:
Figure 17. First member of a family of 4harmonic 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 9vertex are 4vertex 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 8vertex are 4vertex 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 7vertex are 4vertex then and . The equation results that this case is impossible. Also, if then and , then since some of vertices adjacent to 7vertex are 4vertex 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 6vertex are 4vertex then and . So this contradiction with . Then this case is impossible.
Subcase 28:
(64)
since some vertices adjacent to 6vertex are 4vertex 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 5vertex are 4vertex 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 5vertex are 4vertex then and that this contradiction with . Therefore this case is impossible.
Subcase 32:
(70)
Some vertices adjacent to 5vertex are 4vertex then and that this contradiction with . Thus this case is impossible.
Subcase 33:
(71)
Since some vertices adjacent to 5vertex are 4vertex 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 ccyclic 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, 3harmonic graphs as follow:
5. Conclusions
Let # r(c) and #nr(c) be denote the number of connected ccyclic regular and nonregular harmonic graphs, respectively, for a fixed value c. According to fined results, the number of harmonic graphs as follows.
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