www.i-csrs.org
Available free online at http://www.geman.in
Some Results on Harmonic Graphs
A. Mahmoodi Department of Mathematics
Payame Noor University I. R. of Iran
E-mail: [email protected] (Received: 25-1-13 / Accepted: 20-9-13)
Abstract
A graph G is defined to be harmonic if there is a constant λ (necessarily a natural number) such that, for every vertex v, the sum of the degrees of the neighbors of v equals λdG(v) where dG(v) is the degree of v. In this paper, we investigate the effects of some operations on harmonic graphs. Here, we present some methods to construct new harmonic graphs from existing ones. Among other results it is shown that complement of a harmonic graph is harmonic if and only if it is a regular graph.
Keywords: Trees, eigenvalues, graph operations, harmonic graphs.
1 Introduction
We will consider only simple graphs, that is finite and undirected without loops or multiple edges. If G is a graph with vertex set {1, . . . , n}, the adjacency matrix of G is an n×n matrix A = (aij), where aij = 1, if there is an edge between the vertices i and j, and 0 otherwise. The eigenvalues of G are the eigenvalues ofA. The vertex set and edge set of graph G is denoted byV(G) and E(G), respectively. Also, degree of a vertex v ∈ V(G) and the set of neighbors of v are denoted by dG(v) and NG(v), respectively. A vertex of degree k will be referred to as a k-vertex. In addition, vertices of degree one are called pendent.
A graphG is defined to beharmonicif there is a constant λ (necessarily a natural number) such that, for every vertex v, the sum of the degrees of the
neighbors ofv equalsλdG(v). It is easy to see that above definition are equiva- lent toAd(G) = λd(G) i.e., the graphGis harmonic if and only ifd(G) is one of its eigenvectors, where d(G) denotes the column-vector (dG(v1), . . . , dG(vn))t. Clearly,λis the eigenvalue corresponding to the eigenvectord(G). Suppose G is a harmonic graph, then there isλ such that
λdG(vi) = X
(vi,vj)∈E(G)
dG(vj) (1)
for alli= 1,2, . . . , n. Summing the expressions (1) over all i= 1,2, . . . , n and observing that each summand dG(vj) is counted dG(vj) times, we obtain
λ X
1≤i≤n
dG(vi) = X
1≤i≤n
X
(vi,vj)∈E(G)
dG(vj) (2) So, we have
λ= 1
2|E(G)| X
1≤i≤n
d2G(vi). (3) Clearly, a graph G isλ-harmonic if and only if A2j =λAj holds. Where j is column vector whose entry is one.
Harmonic graphs appeared for the first time in [1] where they were called dual-degree-regular graphs. Almost ten years later, they reappeared in [4, 3]
under the present name and in connection with counting walks in a graph. All (finite or infinite) harmonic trees were constructed in [6]. All finite harmonic graphs with up to four independent cycles were characterized in [1] where it was also shown that, while the number of finite harmonic trees is infinite, the number of finite harmonic graphs with a fixed positive cyclomatic number is finite.
The following elementary properties of harmonic graphs result from defini- tion and the well-known spectral properties of graphs [2](cf. [1, pp. 18–20]).
Lemma 1. Let G be a connected λ-harmonic graph and |E(G)|=m.
(i) λ is the greatest eigenvalue of G and its multiplicity is one.
(ii) If m≥1 then λ≥1.
(iii) λ = 1 if and only if G=K2.
2 Main Results
In view of Lemma1 it is reasonable to restrict our considerations to connected non-regular graphs. In [6], all harmonic finite trees were determined.
Letλbe a positive integer. Construct the tree Tλ in the following manner.
The tree 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 pendent, i.e., eachλ-vertex is connected to λ−1 pendent vertices and to the (λ2 −λ+ 1)-vertex. The following theorem is proved in [6].
Theorem 1. For any positive integerλ there exists a uniqueλ-harmonic tree, isomorphic toTλ.
It is worth that one asks are complement of these trees harmonic? In the following theorem, we provide negative answer to this question except in the case λ= 1. To prove the theorem, we need next technical lemma.
Lemma 2. Let G be a λ-harmonic non-trivial graph with n vertex. Then its complementG¯ is a µ-harmonic graph if and only if dG¯(vj) =
P
i6=jdG(vi)−λdG(vj) n−1−µ
for all 1≤j ≤n.
Proof. Suppose that ¯G is a µ-harmonic graph and let ¯A denote its ad- jacency matrix. Then we have ¯A(n − 1− dG(v1), . . . , n − 1 − dG(vn))t = µ(dG¯(v1), . . . , dG¯(vn))t. Using A+ ¯A=J−I, one can obtain following equiv- alent equalities.
(n−1) ¯Aj −(J −I−A)
dG(v1) ... dG(vn)
=µ
dG¯(v1) ... dG¯(vn)
⇐⇒(n−1)
dG¯(v1) ... dG¯(vn)
−
P
i6=1dG(vi) ... P
i6=ndG(vi)
+λ
dG(v1) ... dG(vn)
=µ
dG¯(v1) ... dG¯(vn)
⇐⇒(n−1−µ)
dG¯(v1) ... dG¯(vn)
=
P
i6=1dG(vi)−λdG(v1) ...
P
i6=ndG(vi)−λdG(vn)
.
On the other hand,µ6=n−1 since Gis a non-trivial graph. Therefor, we are
done.
Theorem 2. Let G be a λ-harmonic non-trivial graph with n vertex. Then its complement G¯ is a µ-harmonic graph if and only if G is a regular graph.
Proof. The implication “⇐=” is clear. To prove the other, suppose that ¯G is a µ-harmonic graph. By Lemma2, for 1≤j ≤n and 1≤k≤n, we have
dG¯(vj) = 2|E(G)| −(1 +λ)dG(vj)
n−1−µ (4)
dG¯(vk) = 2|E(G)| −(1 +λ)dG(vk)
n−1−µ . (5)
These equalities imply that (−1 + 1 +λ
n−1−µ)dG(vj) = (−1 + 1 +λ
n−1−µ)dG(vk).
Now, one can deduce that dG(vj) = dG(vk) provided that µ 6= n−2−λ.
Then, we may assume that µ = n−2−λ. Using this together with (4), we have (n−1)(λ + 1) = 2 | E(G) |. So, application [2, Theorem3.8], one can obtain 2|E(G)|≥n(n−1). Therefor, since Gis a simple graph, this implies
that it is a complete graph.
As said before, using Theorem2, we can characterize theµ-harmonicity of the complement of aλ-harmonic tree.
Corollary 1. LetGbe aλ-harmonic tree. Then its complement isµ-harmonic if and only if λ= 1 and µ= 0.
In continue, we give some methods to construct new harmonic graphs from existing ones.
The product G×H of graphs G and H is a graph such that the vertex set of G×H is the Cartesian product V(G)×V(H); and any two vertices (u, u0) and (v, v0) are adjacent in G×H if and only if u is adjacent with v and u0 is adjacent with v0. Define the Kronecker productA⊗B of two matrices A and B to be the matrix we get by replacing theij-entry of A byAijB, for alli and j.
Theorem 3. Let G be a λ-harmonic graph and H be a λ0-harmonic graph.
Then G×H is a λλ0-harmonic graph.
Proof. Suppose that A and B are adjacency matrices of G and H, respec- tively. So, by [5, Section 9.7] adjacency matrices of G×H is A⊗B and we have
(A⊗B)2(jn⊗jm) = (A⊗B)(Ajn⊗Bjm) =A2jn⊗B2jm
=λAjn⊗λ0Bjm =λλ0(A⊗B)(jn⊗jm).
This completes the proof.
The Cartesian product GH of graphs G and H is a graph such that the vertex set ofGH is the Cartesian productV(G)×V(H); and any two vertices (u, u0) and (v, v0) are adjacent in GH if and only if either u = v and u0 is adjacent with v0 in H, or u0 = v0 and u is adjacent with v in G. Suppose that G and H are two r and s-regular graphs, respectively. In this case we knowGH is (r+s)-regular and harmonic graph. There are many examples
show that regularity is necessary toGH be harmonic. For example consider that K2T2 which is not harmonic. In this case K2 and T2 are 1-harmonic and 2-harmonic, respectively. Also, one can see it is possible to choose both graphsλ-harmonic but their Cartesian product is not harmonic. Next simple example shows this.
Example 1. Let G = T2 and H = C3. They are 2-harmonic graphs, but T2C3 is not harmonic.
Theorem 4. Let G and H are two λ-harmonic graphs. Then GH is µ- harmonic graph if and only if G and H are regular graphs.
Proof. As said before, one implication is obvious. To prove the other, sup- pose thatA and B are adjacency matrices of Gand H, respectively. Then by [5, Section 9.7] adjacency matrices ofGH isIn⊗B+A⊗Im wheren andm denote the order ofGand H, respectively. SinceGH is aµ-harmonic graph, we have (In⊗B +A⊗Im)2(jn⊗jm) = µ(In⊗B +A⊗Im)(jn⊗jm). Let (d1, . . . , dn) and (d01, . . . , d0n) denote degree vertices of G and H, respectively.
So, we will have
(In⊗B+A⊗Im)2(jn⊗jm)
= (In⊗B+A⊗Im)(jn⊗Bjm+Ajn⊗jm)
=jn⊗B2jm+ 2(Ajn⊗Bjm) +A2jn⊗jm
=jn⊗λBjm+ 2( d1 · · · dn t
⊗ d01 · · · d0m t
) +λAjn⊗jm
=µ d01+d1 · · · d0m+d1 · · · d01+dn · · · d0m+dn t
.
Now, for (1≤i≤n) and (1 ≤j ≤m), we get mnequations λd0j +λdi+ 2did0j =µ(d0j +di).
For i = 1 and 1 ≤ j ≤ m, one can obtain from m first equations d01 = d02 =
· · ·=d0m. ThereforeH is a regular graph. We note that two graphsGH and HG are isomorphic, so by similar method,G is a regular graph.
Let G and H be two graphs with disjoint vertex sets V1 and V2. The join graphG∨H is the graph with vertex set V1∪V2 and edge setE(G)∪E(H) by adding all of the edges from vertices in G to those in H. It seems that if both of Gand H are regular, then G∨H is harmonic. But this is not the case for example consider K2∨Cn, wheren ≥4.
Theorem 5. Let Gbe ar-regular graph of order n andH be as-regular graph of orderm. Then G∨H is µ-harmonic graph if and only if r+m=s+n.
Proof. It is suffices to prove sufficiency. Suppose thatG∨H is µ-harmonic graph andv ∈V(G). So, one can obtain
µ(dG(v) +m) = X
u∈NG∨H(v)
dG∨H(u)
= X
u∈NG(v)
dG∨H(u) + X
u∈NH(v)
dG∨H(u)
=r(r+m) +m(s+n).
Similarly, forv0 ∈H we haveµ(dH(v) +n) =s(s+n) +n(r+m). Using above relations, we get
µ= r(r+m) +m(s+n)
r+m = s(s+n) +n(r+m) s+n .
Then one can deduced that (r +m)(rs−nm) = (s+n)(sr −mn). On the other hand, we know thatr < nand s < m. Therefore r+m=s+n.
Corollary 2. Let G andH be twor-regular graphs of order n and m, respec- tively. Then G∨H is µ-harmonic graph if and only if m=n.
Regularity for both graphs G and H in Theorem5 is necessary. There are many examples which show that although one of them is regular but their join is not.
Example 2. Let G=k2 and H =T2. Then k2∨T2 is not harmonic.
Acknowledgements:
This research was supported by grants from Payame Noor University. The author is indebted to Payame Noor University for support.
References
[1] B. Borovi´canin, S. Gr¨unewald, I. Gutman and M. Petrovi´c, Harmonic graphs with small number of cycles,Discrete Math., 265(2003), 31-44.
[2] D.M. Cvetkovi´c, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications (3rd ed.), Johann Ambrosius Barth, Heidelberg, (1995).
[3] A. Dress and I. Gutman, Asymptotic results regarding the number of walks in a graph,Appl. Math. Lett., 16(3) (2003), 389-393.
[4] A. Dress and I. Gutman, On the number of walks in a graph, Appl. Math.
Lett., (To appear).
[5] C. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, (2001).
[6] S. Gr¨unewald, Harmonic trees, Appl. Math. Letters, (To appear).
