Thomas Gardemann, Katja Mnius

Institute of Mathematics, University of Wrzburg

katja.moenius@mathematik.uni-wuerzburg.de

We construct new families of integral graphs by considering complete products, unions and point identifications of complete graphs and complete bipartite graphs. In particular, we find a relation between arithmetic series and the integrality of complete products.

Keywords: integral graph, eigenvalues, graph products Mathematics Subject Classification: 05C50, 05C76

DOI: 10.5614/ejgta.2021.9.1.18

1. Introduction

The notion of an integral graph, that is, a graph having integral eigenvalues only, was first introduced by Harary and Schwenk [5] in 1973/74. All graphs considered in this paper are simple, i.e. undirected and without loops or multiple edges. The quest of characterizing all integral graphs seems to be a challenging project. There are several infinite families of integral graphs known (cf. [5, 4, 7, 6, 1]), but they appear rarely compared to the huge number of graphs at all. Thus, there is still no satisfying answer to Harary's and Schwenk's question 'Which graphs have integral spectra?'. Wang et. al. [6, 7] and also Hansen et. al. [4] introduced new families of integral graphs by combining common examples of integral graphs, like complete graphs or complete bipartite graphs. Let G¹ = (V1, E1) and G² = (V2, E2) be two graphs, then the union G¹ ∪ G² of G¹ and G² is the graph with vertex set V¹ ∪ V² and edge set E¹ ∪ E2. The notion aG¹ is short for the a-folded union G¹ ∪ G¹ ∪ . . . ∪ G¹ | {z } a . In the following we write v ∼ w for adjacent vertices

Received: 15 November 2019, Revised: 12 February 2021, Accepted: 28 February 2021.

v and w. The direct product \(G_1 \times G_2\) is the graph with vertex set \(V_1 \times V_2\) and two vertices \((v_1, v_2), (v_1', v_2') \in V_1 \times V_2\) are adjacent in \(G_1 \times G_2\) if and only if \(v_1 \sim v_1'\) in \(G_1\) and \(v_2 \sim v_2'\) in \(G_2\). The graph \(G_1 \square G_2\) denotes the cartesian product of \(G_1\) and \(G_2\) and consists of vertices \(V_1 \times V_2\) where two vertices \((v_1, v_2), (v_1', v_2') \in V_1 \times V_2\) are adjacent in \(G_1 \square G_2\) if and only if either \(v_1 = v_1'\) and \(v_2 \sim v_2'\) or \(v_1 \sim v_1'\) and \(v_2 = v_2'\). Note that if \(G_1\) and \(G_2\) are integral graphs, then the graphs \(G_1 \cup G_2\), \(G_1 \times G_2\) and \(G_1 \square G_2\) are integral, too, and if, in addition, \(G_1\) and \(G_2\) are regular, then also the respective complement graphs \(G_1\) and \(G_2\) are integral. A proof for this can be found in [2].

In this paper, we construct new families of integral graphs by considering the following two products:

Definition 1.1. Let \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) be two graphs, then the complete product \(G_1 \nabla G_2\) has vertex set \(V_1 \cup V_2\) and \(v_1\) and \(v_2\) are adjacent in \(G_1 \nabla G_2\) if and only if either \(v_1 \in V_1\) and \(v_2 \in V_2\) or \(v_1\) and \(v_2\) are adjacent in \(G_1\) or \(G_2\).

Definition 1.2. Let \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) be two graphs and let \(v_1 \in V_1\), \(v_2 \in V_2\). Then the point identification \(G_1 \bullet G_2\) arises from setting \(v_1 = v_2\).

The graph obtained by applying a point identification a-times to the same graph G and the same vertex of G is denoted by \(G^{a}\).

Note that these two products are not closed under integrality. However, the following lemma stated by Hansen et. al. [4] characterizes all complete products of regular graphs with integral eigenvalues:

Lemma 1.1. For i=1,2 let \(G_i\) be regular graphs of degree \(r_i\) with \(n_i\) vertices. The complete product \(G_1 \nabla G_2\) is an integral graph if and only if both, \(G_1\) and \(G_2\), are integral graphs and there exists \(k \in \mathbb{Z}\) such that the integrality condition

\[n_1 n_2 = k(k + r_1 - r_2) \tag{1}\]

holds.

In Section 2 we construct new families of integral graphs by considering complete products satisfying Lemma 1.1. In particular, we study families of integral graphs of the form \(G_1 \nabla a G_2\) and provide relations between the parameter a and some arithmetic series. In Section 3 we investigate point identifications of integral graphs such as complete graphs and complete bipartite graphs. We also find new families of integral graphs of the form \(K_{m,n}^{a}\). Throughout the paper, \(K_{m,n}\) denotes a complete bipartite graphs with bipartitions of order m and m, m0 denotes a complete graph of order m1, and m2 denotes the graph obtained by deleting the vertex m3 of m4 and all its adjacent edges.

2. Integral complete products and airthmetic series

Lemma 1.1 provides a nice characterization of integral complete products of regular graphs. However, it is not easy to find families of such graphs satisfying Equation (1). Some examples are stated in the following theorem:

Theorem 2.1. Every graph of any of the infinite families K1∇(2n − 3)Kn−1, K2∇nKn−² and Km∇((m − 1)(n − 1))Kⁿ is integral.

Proof. We show that each graph of these families satisfy the respective integrality condition. Since all graphs are complete products of integral regular graphs, our statement therefore follows from Lemma 1.1.

Every graph of the first family K1∇(2n − 3)Kn−¹ = Kⁿ 2n−3 • satisfies the integrality condition

\[(2n-3)(n-1) = k(k + (n-2))\]

for k = n − 1 ∈ Z.

The graph K² is regular of degree one with two vertices and nKn−² is regular of degree n−3 with n(n − 2) vertices. Thus, the integrality condition of K2∇nKn−² is

\[2n(n-2) = k(k + (n-4))\]

and indeed holds for k = n ∈ Z.

Similarly, we can see that the integrality condition of Km∇((m − 1)(n − 1))Kⁿ is

\[m(m-1)(n-1)n = k(k + (m-1) - (n-1)).\]

This equation has integer solutions k = mn − m and k = n − mn.

This theorem motivates the question, for which a ∈ N the graph Km∇aKⁿ is integral. Some notable observations are stated in the next result, which is also a consequence of Lemma 1.1.

Theorem 2.2. Let a, b ∈ N. Furthermore, let H be an integral regular graph and G¹ and G² be regular graphs.

• 1. The graph H∇aH is integral if and only if a is a square.
• 2. The graph G1∇aG² is integral if and only if the graph G2∇aG¹ is integral.
• 3. The graph aG1∇bG² is integral if and only if the graph G1∇abG² is integral.

Proof. The integrality condition for H∇aH is a|H| ² = k 2 . Therefore, the first statement follows from Lemma 1.1. If G¹ or G² is non-integral, then by Lemma 1.1 neither G1∇aG² nor G2∇aG¹ is integral. On the other hand, if both graphs, G¹ and G2, are integral, G1∇aG² and G2∇aG¹ satisfy the same integrality condition since k(k + (r¹ − r2)) = −k(−k + (r² − r1)). This implies the second statement and the third statement follows easily from the second one.

Besides this symmetry aspect, we also found that for fixed n, m ∈ N the parameters a ∈ N, for which the graphs Kn∇aK^m are integral, form some arithmetic series. The next theorem provides several new infinite families of integral graphs:

Theorem 2.3. Let p, q, r, t, u, n ∈ N and

\[\begin{split} s_p &= \sum_{i=1}^p a_i \quad \text{with} \quad a_i = 1 + (i-1)2n, \\ s_q &= \sum_{i=1}^q b_i \quad \text{with} \quad b_i = (2n-1) + (i-1)2n, \\ s_r &= \sum_{i=1}^r c_i \quad \text{with} \quad c_i = 1 + (i-1)n, \\ s_t &= \sum_{i=1}^t d_i \quad \text{with} \quad d_i = (n-1) + (i-1)n, \\ s_u &= \sum_{i=1}^u e_i \quad \text{with} \quad e_i = -5 + (i-1)24. \end{split}\]

Then, every graph of any of the families K1∇spKn, K1∇sqKn, K2∇srKn, K2∇stKⁿ and K3∇(6+ su)K⁴ is integral.

Proof. We observe that

\[s_p = \sum_{i=1}^p (1 + (i-1)2n) = p \frac{2 + (p-1)2n}{2} = np^2 - np + p.\]

By Lemma 1.1, the graph K1∇spKⁿ is integral if and only if there exists k ∈ Z such that ns^p = n 2p ² − n ²p + np = k(k − (n − 1)) holds. Indeed, this is true for k = pn. The remaining cases can be proven analogously.

In view of the latter theorem and several computer experiments we conjecture the following:

Conjecture 1. Let a, m, n ∈ N and G = Km∇aKn. If G is integral, then there exists an arithmetic series z+s^p for p ∈ N and z ∈ Z such that a ∈ z+s^p and all graphs of the family Km∇(z+sp)Kⁿ are integral.

Given integral regular graphs G1, G² and H1, H2, the next theorem provides a relation between the integrality of G1∇aG² and H1∇bH² for a, b ∈ N.

Theorem 2.4. Let a ∈ N and G1, G² be integral regular graphs of degree r¹ and r2, respectively, and let H1, H² be integral regular graphs of degree s¹ and s2, respectively. If

\[s_1 - r_1 = s_2 - r_2\] and \(\frac{a|G_1||G_2|}{|H_1||H_2|} \in \mathbb{N},\)

then the graph G1∇aG² is integral if and only if the graph

\[H_1 \nabla \frac{a|G_1||G_2|}{|H_1||H_2|} H_2\]

is integral.

Proof. By Lemma 1.1, the graph G1∇aG² is integral if and only if there is k ∈ Z with

\[a|G_1||G_2| = k(k + (r_1 - r_2)). (2)\]

Since s¹ − r¹ = s² − r2, we have that r¹ − r² = s¹ − s² and, therefore, Equation (2) is equivalent to

\[\frac{a|G_1||G_2|}{|H_1||H_2|}|H_1||H_2| = k(k + (s_1 - s_2)),\]

which equals the integrality condition of H1∇ a|G1||G2| ^|H1||H2^| H2.

Hence, the integrality of direct products G1∇aG² can be verified by considering suitable complete graphs K^r1 , K^r2 in the sense that

\[G_1 \nabla a G_2\] is integral \(\iff K_{r_1} \nabla \frac{a|G_1||G_2|}{r_1 r_2} K_{r_2}\) is integral.

The following corollary provides some explicit examples:

Corollary 2.1. Let a, m, n ∈ N.

• 1. The graph Km∇(Kⁿ × K2) is integral if and only if Km∇2Kⁿ is integral.
• 2. The graphs

\[\overline{K_{anm}}\nabla 2K_{n+1}, \quad \overline{K_{anm}}\nabla (K_{n+1}\times K_2)\]

and

\[\overline{K_m}\nabla(a(n+1))(K_n\Box K_2)\]

are integral if and only if one of them is integral.

• 3. The graph Ka∇Km,m is integral if and only if K2a∇K^m is integral.
• 4. The graph Km,m∇aKn,n is integral if and only if Km∇4aKⁿ is integral.

3. Constructions of integral graphs by point identifications

We now focus on point identifications in order to construct new families of integral graphs.

Lemma 3.1. Let G¹ and G² be graphs and let v be a vertex of G¹ and w be a vertex of G2. Then the point identification v = w yields the following characteristic polynomials:

1. \[\chi(G_1 \bullet G_2, x) = \chi(G_1, x)\chi(G_2 - w, x) + \chi(G_1 - v, x)\chi(G_2, x) - x\chi(G_1 - v, x)\chi(G_2 - w, x)\]

2. \[\chi(G_1^a, x) = \chi^{a-1}(G_1 - v, x)(a\chi(G_1, x) - (a-1)x\chi(G_1 - v, x)).\]

Proof. A proof of the first statement can be found in the book by Cvetkovic et. al. [3]. For the ´ proof of the second statement we use induction over a. For a = 2 we get

\[\chi(G_1 \bullet G_1, x) = 2\chi(G_1, x)\chi(G_1 - v, x) - x\chi^2(G_1 - v, x)\]
= \(\chi(G_1 - v, x)(2\chi(G_1, x)) - x\chi(G_1 - v, x).\)

For the induction step we use the equality χ(G¹ a • −v, x) = χ a (G¹ − v, x) and, therefore, get

\[\chi(G_1^{a+1}, x) = \chi(G_1^a, x)\chi(G_1 - v, x) + \chi(G_1^a, v, x)\chi(G_1, x) - x\chi(G_1^a, v, x)\chi(G_1 - v, x)\] \[= (\chi^{a-1}(G_1 - v, x)(a\chi(G_1, x) - (a - 1)x\chi(G_1 - v, x))) \times \chi(G_1 - v, x) + \chi^a(G_1 - v, x)\chi(G_1, x) - x\chi^a(G_1 - v, x)\chi(G_1 - v, x)\] \[= \chi^a(G_1 - v, x)((a + 1)\chi(G_1, x) - ax\chi(G_1 - v, x)).\]

Starting with a complete graph Kn, we observe that Kⁿ a • = K1∇aKn−1. Thus, by Lemma 1.1 we can easily deduce the following corollary:

Corollary 3.1. The graph Kⁿ a • is integral if and only if there exists k ∈ Z such that a(n − 1) = k(k + (n − 2)).

These families of graphs were already studied in Section 2. Therefore, a next step is to consider graphs of the form K^m •Kⁿ for m 6= n. But computer experiments showed that there is no integral graph of this form for 1 ≤ m, n ≤ 50, and, moreover, not even an integral graph of the form (K^l • Km) • Kⁿ with 1 ≤ l, m, n ≤ 50. Since the search of integral graphs within these families of graphs therefore seems to be a non-promising approach, we consider point identifications of complete bipartite graphs next. In particular, we could prove the following:

Theorem 3.1. Let a, m, n ∈ N. The graph Km,n a • is integral if and only if (m−1)n and n(a+m−1) are squares.

Proof. It is well-known that the characteristic polynomial χ of a complete bipartite graph Km,n equals

\[\chi(K_{m,n}, x) = x^{m+n-2}(x^2 - mn).\]

Thus, together with Lemma 3.1, we get that

\[\chi(K_{m,n} \overset{a}{\bullet}, x) = \chi^{a-1}(K_{m-1,n}, x)(a\chi(K_{m,n}, x) - (a-1)x\chi(K_{m-1,n}, x))\] \[= (x^{m+n-3}(x^2 - (m-1)n))^{a-1} \times \times (ax^{m+n-2}(x^2 - mn) - (a-1)x^{m+n-2}(x^2 - (m-1)n))\] \[= x^{a(m+n-3)+1}(x^2 - (m-1)n)^{a-1} \times \times (a(x^2 - mn) - (a-1)(x^2 - (m-1)n)).\]

Assuming all roots of χ to be integers, (m − 1)n therefore has to be a square. In particular, the last factor of χ is zero if and only if 0 = x ² − n(a + m − 1). This implies the statement.

With this theorem we again find new families of integral graphs:

Corollary 3.2. Let \(a, m, n \in \mathbb{N}\). Then, the following graphs are integral:

1. \[K_{n^2+1,n^2} \stackrel{(n+1)^2-n^2}{\bullet}\],

2. \[K_{n+1,n} \stackrel{(a^2-1)n}{\bullet}\],

3. \[K_{m,n} \stackrel{(m-1)(a^2-1)}{\bullet} \text{ if } \sqrt{(m-1)n} \in \mathbb{Z}.\]

In particular, this corollary shows that for every \(m, n \in \mathbb{N}\) with \(\sqrt{(m-1)n} \in \mathbb{Z}\) there exist infinitely many integral graphs of the form \(K_{m,n}^{\phantom{m}\bullet}\) for \(a \in \mathbb{N}\).

References

• [1] C. Adiga, B.R. Rakshith, and K.N.S. Krishna, Spectra of extended neighborhood corona and extended corona of two graphs, Electronic Journal of Graph Theory and Applications 4 (1) (2016), 101–110.
• [2] A.E. Brouwer and W.H. Haemers, Spectra of Graphs. Springer-Verlag New York, 1st edition (2012).
• [3] D.M. Cvetković, M. Doob, and H. Sachs, Spectra of Graphs: Theory and Applications. Academic Press, 1st edition (1980).
• [4] P. Hansen, H. Mélot, and D. Stevanović, Integral complete split graphs, Univerzitet u Beogradu. Publikacije Elektrotehničkog Fakulteta. Serija Matematika 13 (2002), 89–95.
• [5] F. Harary and A.J. Schwenk, Which graphs have integral spectra?, pages 45–51. Springer Berlin Heidelberg (1974).
• [6] L. Wang, H. Broersma, C. Hoede, X. Li, and G. Still, Some families of integral graphs, Discrete Mathematics 308 (2008), 6383–6391.
• [7] L. Wang, X. Li, and S. Zhang, Construction of integral graphs, Applied Mathematics-A Journal of Chinese Universities Series B 15 (2000), 239–246.