Bulletin T.CXXIII de l’Académie Serbe des Sciences et des Arts - 2002 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 27

TETRACYCLIC HARMONIC GRAPHS

B. BOROVIĆANIN, I. GUTMAN, M. PETROVIĆ

(Presented at the 1st Meeting, held on February 22, 2002)

A b s t r a c t. A graph G on n vertices v_{1}, v_{2}, …, v_{n} is said to be harmonic if (d(v_{1}), d(v_{2}), …, d(v_{n}))^{t} is an eigenvector of its (0, 1)-adjacency matrix, where d(v_{i}) is the degree (= number of first neighbors) of the vertex v_{i} , i = 1, 2, …, n. Earlier all acyclic, unicyclic, bicyclic and tricyclic harmonic graphs were characterized. We now show that there are 2 regular and 18 non-regular connected tetracyclic harmonic graphs and determine their structures.

AMS Mathematics Subject Classification (2000): 05C50, 05C75 Key Words: Harmonic graphs, Spectra (of graphs), Walks

1. Introduction

Let G = (V (G), E(G)) be a graph with |V (G)| = n vertices and |E(G)| = m edges, whose vertices are labeled by v_{1}, v_{2}, …, v_{n}. A walk of length k in G is an ordered (k + 1)-tuple of vertices, (v_{i_{0}}, v_{i_{1}}, …, v_{i_{k}}) , such that for all j = 1, …, k , (v_{i_{j−1}}, v_{i_{j}}) ∈ E(G) . The number of all walks of length k in the graph G is denoted by W_{k}(G) . It is both consistent and convenient to set W_{0}(G) = n; note also that W_{1}(G) = 2m.

In a recent work [7] the way in which W_{k}(G) increases with k was studied. For this an auxiliary quantity Δ_{k}(G) was introduced [4, 5], defined as

Δ_{k}(G) = W_{k+1}(G) W_{k−1}(G) − W_{k}(G)^{2} .

It is easy to show that the equality Δ_{k}(G) = 0 holds for all k ≥ 1 if and only if G is a regular graph. There exist graphs for which the equality Δ_{k}(G) = 0 holds for all k > 1 . These were named harmonic graphs [4, 5] and may be viewed as a peculiar generalization of regular graphs. Grünewald [6] determined all harmonic trees (for details see below) and the present authors together with Grünewald determined all unicyclic, bicyclic and tricyclic harmonic graphs [1]. In this work we go a step further and find all tetracyclic harmonic graphs. In order to do this we need some preparation.

If the graph G has p components, then c = m − n + p is the cyclomatic number of G and this graph is said to be c-cyclic. In particular, if c = 4 we speak of tetracyclic graphs. If the graph G is connected (p = 1) and c = 0 then G is a tree.

The number of first neighbors of the vertex v_{i} is the degree of this vertex and is denoted by d(v_{i}) . A vertex of degree k will be referred to as a k-vertex. The column–vector (d(v_{1}), d(v_{2}), …, d(v_{n}))^{t} is denoted by d(G) .

The number of k-vertices is denoted by n_{k}. Then

∑_{k≥0} n_{k} = n ,  (1)

∑_{k≥0} k n_{k} = 2m .  (2)

A graph G is said to be harmonic [4, 5] if there exists a constant λ, such that the equality

λ d(v_{i}) = ∑_{(v_{i},v_{j})∈E(G)} d(v_{j})  (3)

holds for all i = 1, 2, …, n. The fact that the property W_{k}(G) = 0 for all k > 0 is a consequence of Eq. (3) has been demonstrated elsewhere [4, 5].

In [1] the following connection to graph spectral theory [2] was pointed out. If A(G) is the adjacency matrix of G then the system of equations (3) is equivalent to

A(G) d(G) = λ d(G) .  (4)

Consequently, the graph G is harmonic if and only if d(G) is one of its eigenvectors. A graph satisfying Eqs. (3) and (4) will be referred to as a λharmonic graph. Clearly, λ is the eigenvalue associated with the eigenvector d(G) . It is easy to show [1] that λ must be a non-negative integer.

Summing the expressions (3) over all i = 1, 2, …, n we obtain

∑_{k≥0} k(k − λ) n_{k} = 0 ,  (5)

which is a necessary, but not sufficient, condition that harmonic graphs must obey.

2. Some Auxiliary Results

In our previous work [1] a number of results were obtained, applicable either to all harmonic graphs or to harmonic graphs with small number of cycles. Here we re-state (without proof) some of these results, needed for the proof of our main result, i. e., of Theorem 10. These are the Lemmas 1, 2, 4, 5, 6, 7 and 8. The result stated here as Theorem 3 is due to Grünewald [6]. We also state (with proof) a novel Lemma 9.

Lemma 1. (a) Let the graph G′ be obtained from the graph G by adding to it an arbitrary number of 0-vertices. Then G′ is harmonic if and only if G is harmonic.

(b) If G is a graph without 0-vertices, then G is λ-harmonic if and only if all its components are λ-harmonic.

(c) Every regular graph is harmonic. Every regular graph of degree k is k-harmonic.

Lemma 2. Let G be a connected λ-harmonic graph. Then

(a) λ is the greatest eigenvalue of G and its multiplicity is one;

(b) if m > 0 then λ ≥ 1 ;

(c) λ = 1 if and only if n = 2 and m = 1 .

From Lemma 1 we conclude that it is reasonable to restrict our considerations to connected non-regular graphs. The fact that such harmonic graphs do exist and that their structure is non-trivial became evident after the discovery of Theorem 3 [6].

Let λ be a positive integer. Construct the Grünewald tree T_{λ} in the following manner. T_{λ} has a total of λ^{3} − λ^{2} + λ + 1 vertices, of which one vertex is a (λ^{2} − λ + 1)-vertex, λ^{2} − λ + 1 vertices are λ-vertices and (λ − 1)(λ^{2} − λ + 1) vertices are 1-vertices. Each λ-vertex is connected to λ − 1 1-vertices and to the (λ^{2} − λ + 1)-vertex.

Theorem 3 [6]. For any positive integer λ there exists a unique λharmonic tree, isomorphic to T_{λ}.

Lemma 4. The Grünewald tree T_{2} is the unique connected non-regular 2-harmonic graph.

Bearing in mind Lemmas 2 and 4, in the following we may assume that λ ≥ 3 .

Lemma 5. (a) In a λ-harmonic graph every 1-vertex is adjacent to a vertex of degree λ.

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

(c) In a harmonic graph (with n > 2) no 1-vertex is attached to any vertex of greatest degree.

Lemma 6. If x is a vertex of a λ-harmonic graph, then d(x) ≤ λ^{2}−λ+1 . If d(x) = λ^{2} − λ + 1 then x belongs to a Grünewald tree T_{λ}. Otherwise, d(x) < λ^{2} − λ + 1 .

Lemma 7. Let G ≠ T_{λ} be a connected c-cyclic λ-harmonic graph with λ ≥ 3 . Then c ≥ \frac{1}{2} (λ^{2} − 2 λ + 2) .

Lemma 8. For the λ-harmonic tree, n_{1} = (λ − 1) n_{λ}. For any other connected λ-harmonic graph, n_{1} ≤ (λ − 2) n_{λ}.

For the below considerations is of importance the relation [1]

∑_{k≥0}(k − 2) n_{k} = 2 c − 2  (6)

obtained by combining the equalities (1) and (2) and using the fact that the respective graphs are connected (m = n + c − 1).

Before we formulate our main result – Theorem 10 – we demonstrate the validity of another auxiliary result that will be often used in the proof of Theorem 10.

Lemma 9. Let v be a vertex of a λ-harmonic graph, such that d(v) > λ^{2} − 3 λ + 4 , and let u be a vertex adjacent to v. Then d(u) = λ.

P r o o f. Let v ∈ V (G) , d(v) > λ^{2} − 3 λ + 4 and u, u_{2}, …, u_{d(v)} be the vertices of G adjacent to the vertex v. Assume first that d(u) = λ − 1 . Then, because of (3),

λ d(u) = λ(λ − 1) = d(v) + d(x_{1}) + ⋯ + d(x_{λ−2})

where v, x_{1}, …, x_{d(u)−1} are the vertices adjacent to the vertex u. This yields

d(x_{1}) + ⋯ + d(x_{λ−2}) = λ^{2} − λ − d(v)
< λ^{2} − λ − (λ^{2} − 3 λ + 4)
= 2(λ − 2) .

If follows that there must exist at least one i (i = 1, 2, …, λ − 2) , such that d(x_{i}) = 1 , which because of Lemma 5 (a) is impossible.

Therefore, it cannot be d(u) = λ − 1 .

Consider now the case d(u) = λ − t for some t ≥ 2 . Then from Eq. (3),

λ d(u) = λ(λ − t) = d(v) + d(x_{1}) + ⋯ + d(x_{λ−t−1}) > λ^{2} − 3 λ + 4 + λ − t − 1

i. e.,

λ (λ − t) > λ^{2} − 2 λ + 3 − t

i. e.,

λ (t − 2) < t − 3 .  (7)

This again is a contradiction: for t = 2 inequality (7) becomes 0 < −1 . For t > 2 inequality (7) implies λ < (t − 3)/(t − 2) < 1 which is impossible in view of the assumption λ ≥ 3 .

Thus, it cannot be d(u) < λ − 1 .

Consequently, if d(v) > λ^{2} − 3 λ + 4 and (u, v) ∈ E(G) then it must be d(u) ≥ λ.

If, however, the degree of any neighbor of the vertex v is greater or equal to λ then from

λ d(v) = d(u) + d(u_{2}) + ⋯ + d(u_{d(v)})

there follows that it must be d(u) = d(u_{2}) = ⋯ = d(u_{d(v)}) = λ. This implies Lemma 9. □

3. The Main Result

Theorem 10. There are exactly 18 non-regular connected tetracyclic harmonic graphs, depicted in Fig. 1.

Fig 1. The connected non-regular tetracyclic harmonical graphs

P r o o f. Because of Lemma 7, if c = 4 then λ cannot be greater than 3. Then, in view of Lemmas 2 and 4, we conclude that it must be λ = 3 . By Lemma 6, if D is the maximal vertex degree in a tetracyclic harmonic graph, then D ≤ 6 . From Lemma 5 (b) we then conclude that only the following three cases need to be examined:

Case 1: λ = 3 , D = 6 , Case 2: λ = 3 , D = 5 , Case 3: λ = 3 , D = 4 .

C a s e 1. From Lemma 8 follows that n_{3} − n_{1} ≥ 0 . By means of relation (6), for c = 4 we get

−n_{1} + n_{3} + 2 n_{4} + 3 n_{5} + 4 n_{6} = 6

from which

2 n_{4} + 3 n_{5} + 4 n_{6} − 6 = n_{1} − n_{3} ≤ 0

and we conclude that

n_{4} ≤ 1 ; n_{5} = 0 ; n_{6} = 1 .  (8)

From Eq. (5) we get

−2 n_{1} − 2 n_{2} + 4 n_{4} + 10 n_{5} + 18 n_{6} = 0

which, by taking into account (8), implies

n_{1} + n_{2} = 9 + 2 n_{4} .

According to Lemma 9, a 6-vertex (i. e., a vertex of degree 6) is adjacent only to 3-vertices. The two neighbors of every 3-vertex, adjacent to a 6-vertex, must be a 1 and a 2-vertex. Therefore, n_{1} ≥ 6 , n_{2} ≥ 3 and, consequently, n_{1} + n_{2} ≥ 9 . In what follows we distinguish between two subcases.

S u b c a s e 1.1.

n_{4} = 0 ; n_{5} = 0 ; n_{6} = 1 ; n_{3} = n_{1} + 2 ; n_{1} + n_{2} = 9 (9)

In this case it is easy to see that n_{1} = 6 , n_{2} = 3 , n_{3} = 8 , n_{4} = 0 , n_{5} = 0 , n_{6} = 1 . Each of the three 2-vertices must be adjacent to two 3-vertices (which, in turn, are adjacent to the 6-vertex), and an excess of two 3-vertices remains. Therefore there cannot exist a 3-harmonic graph satisfying the conditions (9).

S u b c a s e 1.2.

n_{4} = 1 ; n_{5} = 0 ; n_{6} = 1 ; n_{3} = n_{1} ; n_{1} + n_{2} = 11 (10)

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 n_{2} ≥ 3 we now have n_{1} = n_{3} ≥ 10 and n_{1} + n_{2} ≥ 13 , which contradicts to the last equality in (10). Therefore, there cannot exist a 3-harmonic graph satisfying the conditions (10).

C a s e 2. Equations (5) and (6) now become

−2 n_{1} − 2 n_{2} + 4 n_{4} + 10 n_{5} = 0
−n_{1} + n_{3} + 2 n_{4} + 3 n_{5} = 6

which together with the relation n_{3}−n_{1} ≥ 0 imply that either n_{4} = 0 , n_{5} = 2 or n_{4} = 1 , n_{5} = 1 or n_{4} = 0 , n_{5} = 1 . We distinguish between three subcases.

S u b c a s e 2.1.

n_{4} = 0 ; n_{5} = 2 ; n_{3} = n_{1} ; n_{1} + n_{2} = 10  (11)

Because of Lemma 9, every 5-vertex is adjacent only with 3-vertices. Therefore n_{3} ≥ 10 and n_{1} ≥ 10 and in view of the last equality in (11), n_{1} = 10 , n_{2} = 0 , n_{3} = 10 , n_{4} = 0 , n_{5} = 2 . Denote the two 5-vertices by u and v. Denote the 3-vertices adjacent to u and v by x_{1}, x_{2}, …, x_{5} and y_{1}, y_{2}, …, y_{5} , respectively. The three neighbors of any 3-vertex are a 5–, a 3– and a 1-vertex. The graph induced by the 3-vertices is 5 K_{2} , and there are either one or three or five edges connecting the vertices {x_{1}, x_{2}, …, x_{5}} and {y_{1}, y_{2}, …, y_{5}}. In view of this, G_{1} , G_{2} and G_{3} (depicted in Fig. 1) are the only 3-harmonic graphs satisfying the conditions (11).

S u b c a s e 2.2.

n_{4} = 1 ; n_{5} = 1 ; n_{3} = n_{1} + 1 ; n_{1} + n_{2} = 7  (12)

By Lemma 9, the 5– and 4-vertices are adjacent only with 3-vertices. Furthermore, no 3-vertex can be simultaneously adjacent to a 5– and a 4vertex. Consequently, n_{3} ≥ 9 , which implies n_{1} = n_{3} − 1 ≥ 8 and n_{1} + n_{2} ≥ 8 . This violates the last equality in (12), and we conclude that there cannot exist a 3-harmonic graph satisfying the conditions (12).

S u b c a s e 2.3.

n_{4} = 0 ; n_{5} = 1 ; n_{3} = n_{1} + 3 ; n_{1} + n_{2} = 5  (13)

If there is a 3-harmonic graph obeying conditions (13), then its vertices have the following properties:

(i) The 5-vertex is adjacent only to 3-vertices (by Lemma 9), and thus n_{3} ≥ 5 and n_{1} = n_{3} − 3 ≥ 2 . (ii) The 1-vertices are adjacent to only those 3-vertices which are adjacent to the 5-vertex. (iii) Every 2-vertex is adjacent to two 3-vertices. Furthermore, n_{2} ≠ 1 , because if it were n_{2} = 1 then the 3-vertex adjacent to this 2-vertex would be adjacent either to another 2-vertex or to a 4-vertex, which both are impossible. (iv) Exactly n_{1} 3-vertices, which are adjacent to the 5-vertex, are adjacent to one 3– and one 1–vertex. Each of the remaining 5−n_{1} 3-vertices, adjacent to the 5-vertex, are adjacent to a pair of 2-vertices.

Bearing in mind the above, the parameters n_{1}, n_{2}, n_{3}, n_{4}, n_{5} may assume the following values:

n_{1} n_{2} n_{3} n_{4} n_{5}
(a) 2 3 5 0 1
(b) 3 2 6 0 1
(c) 5 0 8 0 1

(a) In view of the properties (i)–(iv), we conclude that the graph G_{4} (depicted in Fig. 1) is the only 3-harmonic graph satisfying the values of the parameters n_{i} , i = 1, 2, …, 5 , given under (a) .

(b) The only 3-vertex not adjacent to the 5-vertex, is adjacent to three other 3-vertices, implying that G_{5} is the only 3-harmonic graph with the vertex degree distribution (b) .

(c) Any of the three 3-vertices, which are not adjacent to the 5-vertex, are adjacent only to 3-vertices. The graph induced by these vertices is either K_{3} or P_{3} . Therefore G_{6} and G_{7} are the only 3-harmonic graphs obeying the choice (c) of the parameters n_{i}.

C a s e 3. Equalities (5) and (6) now become

n_{1} + n_{2} = 2 n_{4}
−n_{1} + n_{3} + 2 n_{4} = 6

from which, in view of n_{3} − n_{1} ≥ 0 , there follows that n_{4} may assume the value 1 or 2 or 3. We thus distinguish three subcases.

S u b c a s e 3.1.

n_{4} = 1 ; n_{3} = n_{1} + 4 ; n_{1} + n_{2} = 2  (14)

In this case n_{1} = 0 . Indeed, if it were n_{1} > 0 then the 3-vertex adjacent to a 1-vertex would be adjacent also to two 4-vertices, which is impossible. Therefore, n_{1} = 0 , n_{2} = 2 , n_{3} = 4 , n_{4} = 1 . The 4-vertex must be adjacent to four 3-vertices. Every 3-vertex is adjacent to a 2–, a 3– and a 4-vertex. From this we conclude that G_{8} and G_{9} (depicted in Fig. 1) are the only graphs with the required properties.

S u b c a s e 3.2.

n_{4} = 2 ; n_{3} = n_{1} + 2 ; n_{1} + n_{2} = 4  (15)

The vertices of 3-harmonic graphs obeying conditions (15) have the following properties:

(i) Every 1-vertex is adjacent to a 3-vertex. (ii) n_{1} 3-vertices are adjacent to one 1– and two 4-vertices. The remaining two 3-vertices are adjacent to a 2–, a 3– and a 4-vertex. (iii) Exactly one 2-vertex is adjacent to two 3-vertices. All other 2-vertices are adjacent to a 2– and a 4-vertex. Therefore the number of 2-vertices is odd. (iv) Every 4-vertex is adjacent to an even number of vertices of odd degree (i. e., to an even number of 3-vertices).

From the above follows that the parameters n_{1}, n_{2}, n_{3}, n_{4} may assume two sets of values:

n_{1} n_{2} n_{3} n_{4}
(a) 3 1 5 2
(b) 1 3 3 2

The graphs G_{10} and G_{11} are the only 3-harmonic graphs satisfying conditions (a) and (b) , respectively.

S u b c a s e 3.3.

n_{4} = 3 ; n_{3} = n_{1} ; n_{1} + n_{2} = 6  (16)

This time the vertices have the following properties:

(i) Every 1-vertex is adjacent to a 3-vertex.

(ii) Every 3-vertex is adjacent to one 1– and two 4-vertices. (iii) Every 2-vertex is adjacent to a 4– and a 2-vertex. Therefore the number of 2-vertices is even. (iv) Every 4-vertex is adjacent to an even number of vertices of odd degree (i. e., to an even number of 3-vertices).

In this subcase the following vertex degree distributions may occur:

n_{1} n_{2} n_{3} n_{4}
(a) 6 0 6 3
(b) 4 2 4 3
(c) 2 4 2 3
(d) 0 6 0 3

(a) Taking into account properties (ii) and (iv) we conclude that the 3– and 4-vertices are connected by exactly 12 edges, and that every 4-vertex is adjacent to four 3-vertices. This results in the graph G_{12} .

(b) Taking into account properties (ii) and (iv) we see that the 3– and 4vertices are connected by exactly 8 edges. Further, one 4-vertex is adjacent to four 3-vertices whereas each of the other two 4-vertices is adjacent to one 2-, one 4– and two 3-vertices. This results in the graph G_{13} .

(c) Because of (ii) and (iv) this time two 3-vertices must be adjacent to the same pair of 4-vertices. These two 4-vertices are not adjacent, because otherwise the third 4-vertex would be adjacent to 2-vertices only, which is impossible. Further, every 4-vertex adjacent to 3-vertices is adjacent also to a 2– and a 4-vertex. Taking into account the mutual connectedness of the 2vertices we arrive at the graphs G_{14} and G_{15} , which are the only 3-harmonic species with vertex degree distribution (c) .

(d) Every 4-vertex is adjacent to two 2-vertices and to two 4-vertices. Thus, the 4-vertices must be mutually adjacent. In view of this, and bearing in mind (iii), the only possible solutions are the graphs G_{16} , G_{17} and G_{18} , depicted in Fig. 1.

By this all possible cases have been examined. The proof of Theorem 10 is complete. □

4. The Regular Case

In order to complete the list of connected tetracyclic harmonic graphs we prove the following elementary result.

Theorem 11. There are exactly 2 regular connected tetracyclic harmonic graphs, depicted in Fig. 2.

Fig 2. The connected regular tetracyclic harmonic graphs

P r o o f. A regular graph of degree D has \frac{1}{2} n D edges. If it is connected and tetracyclic, then

\frac{1}{2} n D − n + 1 = 4 i. e., n = \frac{6}{D − 2}

For D = 3, 4, 5 and D ≥ 6 we obtain n = 6, 3, 2 and n < 2 , respectively. Thus only the case D = 3 , n = 6 is possible.

It is well known [3] (and easy to show) that there are exactly two cubic graphs on 6 vertices, the graphs G_{19} and G_{20} depicted in Fig. 2. □

5. Summary

Together with the results reported elsewhere [1, 6] we may now summarize the achievements of the search for harmonic graphs with small number of cycles. For a fixed value of the cyclomatic number c the number of connected c-cyclic regular and non-regular harmonic graphs is denoted by #r(c) and #nr(c), respectively. The following are the known values of #r(c) and #nr(c):

c #r(c) #nr(c)  remark
0  1  ∞  one for each λ ≥ 1
1  ∞  0  one for each n ≥ 3 ; λ = 2
2  0  0
3  1  4  all with λ = 3
4  2  18  all with λ = 3
≥ 5 finite finite

REFERENCES

[1] B. B o r o v i ć a n i n, S. G r ü n e w a l d, I. G u t m a n, M. P e t r o v i ć, Harmonic graphs with small number of cycles, Discrete Math., in press.

[2] D. C v e t k o v i ć, M. D o o b, H. S a c h s, Spectra of graphs – theory and application, Barth, Heidelberg, 1995.

[3] D. C v e t k o v i ć, M. P e t r i ć, A table of connected graphs on six vertices, Discr. Math. 50 (1984), 37–49.

[4] A. D r e s s, I. G u t m a n, On the number of walks in a graph, Appl. Math. Letters, in press.

[5] A. D r e s s, I. G u t m a n, Asymptotic results regarding the number of walks in a graph, Appl. Math. Letters, in press.

[6] S. G r ü n e w a l d, Harmonic trees, Appl. Math. Letters, in press.

[7] I. G u t m a n, C. R ü c k e r, G. R ü c k e r, On walks in molecular graphs, J. Chem. Inf. Comput. Sci. 41 (2001), 739–745.

Faculty of Science University of Kragujevac P. O. Box 60 YU–34000 Kragujevac Yugoslavia