PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 77(91) (2005), 53–60

ON GRAPHS WHOSE REDUCED ENERGY DOES NOT EXCEED 3

Mirjana Lazić

Communicated by Žarko Mijajlović

Abstract. In [3], Lepović described all connected graphs whose reduced energy, i.e., the sum of absolute values of all eigenvalues except the least and the largest ones, does not exceed 2.5. Here we describe all connected graphs whose reduced energy does not exceed 3.

We consider only finite connected graphs having no loops or multiple edges. The vertex set of a graph G is denoted by V (G), and its order (number of vertices) by |G|. The spectrum of such a graph is the family λ_{1} ⩾ λ_{2} ⩾ ⋯ ⩾ λ_{n} of eigenvalues of its 0 − 1 adjacency matrix, and we also write λ_{i}(G) = λ_{i} (i = 1, 2, …, n). The eigenvalue λ_{1}(G) = r(G) is called the spectral radius of G, while the eigenvalue λ_{n}(G) is the least eigenvalue of G.

The sum of eigenvalues |λ_{2}| + |λ_{3}| + ⋯ + |λ_{n−1}| is denoted by T_{1}(G) and called the reduced energy of G. For any real a > 0, we can consider the class of graphs

E_{1}(a) = {G|T_{1}(G) ⩽ a}.

In [3] M. Lepović completely described the class E_{1}(2.5). Here we completely describe the class E_{1}(3), i.e., the class of all connected graphs whose reduced energy does not exceed 3.

Briefly, any graph G ∈ E_{1}(3) is called admissible, and any other graph impossible (or forbidden) for this class.

If H is any connected (induced) subgraph of a graph G, we write H ⊆ G. Making use of the known interlacing theorem [1] we have T_{1}(H) ⩽ T_{1}(G). Whence, we have that any connected subgraph of an admissible graph is also admissible. This implies that the method of forbidden subgraphs can be consistently applied.

Since the complete bipartite graph K_{m,n} belongs to the class E_{1}(a) for every m, n ∈ N we conclude that the class E_{1}(a) is infinite for every constant a > 0.

In order to generate all graphs from the class E_{1}(3) we first determine the complete set of the so-called canonical graphs in this class.

2000 Mathematics Subject Classification: Primary 05C50.

We say that two vertices x, y ∈ V (G) are equivalent in G and denote it by x ∼ y if x is nonadjacent to y, and x and y have exactly the same neighbors in G. Relation ∼ is an equivalence relation on the vertex set V (G). The corresponding quotient graph is denoted by g, and called the canonical graph of G. The graph g is also connected, and we obviously have g ⊆ G. For instance, if G = K_{m_{1},m_{2},...,m_{p}} (p ⩾ 2) is the complete p-partite graph, then its canonical graph is the complete graph K_{p}. The canonical graph of the complete graph K_{n} is the same graph K_{n}.

We say that G is canonical if |G| = |g|, that is if G has no two equivalent vertices. Let g be the canonical graph of G, |g| = k, and N_{1}, N_{2}, …, N_{k} be the corresponding sets of equivalent vertices in G. Then we denote G = g(N_{1}, N_{2}, …, N_{k}), or simply G = (n_{1}, n_{2}, …, n_{k}), where |N_{i}| = n_{i} (i = 1, 2, …, k), understanding that g is a labelled graph. We call N_{1}, …, N_{k} the characteristic sets of G. Obviously, each set N_{i} ⊆ V (G) (i = 1, …, k) consists only of isolated vertices, and if at least one edge between the sets N_{i}, N_{j} (i ≠ j) is present, then all possible edges between these sets are also present.

It was proved in [5] that the characteristic polynomial P_{G}(λ) of the graph G takes the form

(1)  P_{G}(λ) = n_{1} · n_{2} · . . . · n_{k}λ^{n−k} · |\begin{matrix}λ/n_{1} & −ã_{12} & … & −ã_{1k} \\ −ã_{21} & λ/n_{2} & … & −ã_{2k} \\ ⋮ & ⋮ & ... & ⋮ \\ −ã_{k1} & −ã_{k2} & … & λ/n_{k} \end{matrix}|

where n = n_{1} + n_{2} + ⋯ + n_{k} and [ã_{ij}] is the adjacency matrix of the canonical graph g.

If g is the canonical graph of a graph G we have that g ⊆ G whence we obtain

G ∈ E_{1}(a) ⇒ g ∈ E_{1}(a).

Hence, it is very convenient to describe first the set of all canonical graphs from the set E_{1}(a).

We note that many other hereditary problems in the spectral theory of graphs can be reduced to finding first the corresponding sets of canonical graphs.

Creating the complete set of canonical graphs in this paper is based on the following general theorem proved in [6], which can be very valuable for other similar problems.

Theorem A. In all but a sequence of exceptional cases, each connected canonical graph on n vertices (n ⩾ 3) contains an induced subgraph on n − 1 vertices, which is also connected and canonical. The mentioned exceptional cases are the graphs in Fig. 1. (In graphs in Fig. 1 vertices y_{i} and x_{j} are adjacent whenever i ⩽ j).

The above exceptional graphs satisfy the relations T_{0} ⊆ T_{1} ⊆ T_{2} ⊆ · · ·.

Now, we give an important property of the general class E_{1}(a) (a > 0), which is proved in [3]. It is based on Theorem B which is proved in [5].

Theorem B. For every n ∈ N the complete set of canonical graphs which have n non-zero eigenvalues is finite.

[figure: T_{0}; T_{1}; T_{2}; …; …; …; X_{1}; X; a; X_{2}; X_{3}; X_{m}; Y_{1}; Y; b; Y_{2}; Y_{3}; Y_{m}; T_{m}]

Figure 1

Theorem 1. For every constant a > 0, the set of canonical graphs from the class E_{1}(a) is finite.

By a direct inspection of all connected graphs with at most 5 vertices (see, for example, tables in [1]), we find that class E_{1}(3) contains exactly 16 canonical graphs with at most 5 vertices.

Besides, by a direct inspection of spectra of all connected graphs with 6 and 7 vertices, (see, for example [2]) we find that the class E_{1}(3) contains 8 canonical graphs with 6 vertices and no canonical graph with 7 vertices. Therefore, according to Theorem A it follows that the class E_{1}(3) contains no canonical graph of order n > 7.

Theorem 2. There are exactly 24 canonical graphs which belonging to the class E_{1}(3). They are displayed in Fig. 2.

Proposition 1. A graph G = g_{1}(m, n) ∈ E_{1}(3) (m ⩽ n) for all values of parameters m, n.

Proof. Since g_{1} = K_{2}, graph G = K_{m,n} is the complete bipartite graph and it has exactly one positive and one negative eigenvalue. Consequently T_{1}(G) = 0 for any complete bipartite graph K_{m,n}. □

Proposition 2. A graph G = g_{2}(m, n, k) (m ⩽ n ⩽ k) belongs to the class E_{1}(3) if and only if (m, n, k) has one of the following values:

(1, ˙1, ˙1), (2, 6, ˙6), (2, 7, 15), (2, 8, 10), (2, 9, 9), (3, 3, ˙3).

where ṗ means that the corresponding parameter is greater or equal p.

Proof. Since g_{2} = K_{3}, graph G is the complete 3-partite graph K_{m,n,k}. It has only three nonzero eigenvalues, which are the roots of the polynomial (see (1))

P (λ) = λ^{3} − (mn + mk + nk)λ − 2mnk.

Therefore G ∈ E_{1}(3) if and only if |λ_{2}| ⩽ 3, that is if and only if P (−3) ⩾ 0. Whence we easily find the statement. □

[figure: m; n; g_{1}; m; n; k; g_{2}; n; k; m; l; g_{3}; m; n; k; l; g_{4}; m; n; l; k; g_{5}; n; k; l; m; p; g_{6}; m; n; l; p; k; g_{7}; m; n; k; l; p; g_{8}; m; n; k; l; p; g_{9}; m; n; k; l; p; g_{10}; m; n; p; l; k; g_{11}; n; k; l; m; p; g_{12}; m; n; p; l; k; g_{13}; m; k; p; n; l; g_{14}; m; n; l; p; k; g_{15}; m; n; p; l; k; g_{16}; m; n; k; q; p; l; g_{17}; m; n; k; l; q; p; g_{18}; m; n; k; q; p; l; g_{19}; m; n; k; q; p; l; g_{20}; n; k; l; m; q; p; g_{21}; m; n; k; q; p; l; g_{22}; n; k; l; m; q; p; g_{23}; k; l; p; n; m; q; g_{24}] Figure 2

Proposition 3. A graph G = g_{3}(m, n, k, l) (m ⩽ l) belongs to the class E_{1}(3) if and only if (m, n, k, l) has one of the following values:

(1, 2, ˙1, ˙1), (1, ˙1, ˙1, 2), (1, ˙1, 1, 4), (1, 3, ˙1, 9),
(1, 3, 2, 10), (1, 3, 1, 11), (1, 4, ˙1, 5), (1, 4, 1, 7),
(1, 4, 2, 6), (1, 5, ˙1, 4), (1, 5, 1, 6), (1, 5, 2, 5),
(1, 12, 1, 5), (1, 11, 13, 3), (1, 12, 9, 3), (1, 13, 8, 3),
(1, 14, 7, 3), (1, 15, 6, 3), (1, 9, ˙1, 3), (1, 6, 5, 4),
(1, 7, 3, 4), (1, 10, 2, 4), (1, 10, 23, 3), (1, 10, ˙1, 2),
(1, 19, 5, 3), (1, 29, 4, 3), (1, ˙1, 3, 3), (2, 1, 1, ˙1),
(2, 2, ˙1, 2), (2, 3, 11, 2), (2, 4, 5, 2), (2, 2, 5, 3),
(2, 2, 1, 4), (2, 1, ˙1, 5), (3, 1, 1, 5), (3, 1, 2, 4).

Proof. It is easy to check that each of the above graphs belongs to the class E_{1}(3). Next, according to (1) it is easily to see that non-zero eigenvalues of such a graph are determined by equation

λ^{4} − (mn + nk + kl)λ^{2} + mnkl = 0.

Hence, these eigenvalues can be explicitly found. Therefore, it is easy to prove that G = g_{3}(m, n, k, l) ∈ E_{1}(3) if and only if 16mnkl − 36(mn + nk + kl) + 81 ⩽ 0.

Hence we immediately get the statement. □

In a similar way, one can prove the next 19 propositions. The corresponding polynomials which are used in these propositions are determined in [4].

Proposition 4. A graph G = g_{4}(m, n, k, l) (k ⩽ l) belongs to the class E_{1}(3) if and only if (m, n, k, l) has one of the following values:

(1, 1, ˙1, ˙1), (1, 2, 2, ˙1), (1, 3, 2, 4), (1, ˙1, 2, 3),
(2, ˙1, 1, ˙1), (˙1, ˙1, 1, 2), (2, ˙1, 2, 2), (2, 1, 4, ˙1),
(2, 1, 5, 8), (2, 1, 6, 6), (4, 1, 1, ˙1), (4, 2, 2, 2),
(3, 2, 1, 18), (3, 3, 1, 9), (3, 4, 1, 8), (3, 11, 1, 7),
(3, ˙12, 1, 6), (4, 2, 1, 6), (4, ˙1, 1, 5), (5, 1, 1, 6),
(5, 1, 2, 2), (5, ˙1, 1, 4), (6, 3, 1, 4), (7, 1, 1, 4),
(12, 2, 1, 3), (13, 1, 1, 3), (11, ˙1, 1, 3).

Proposition 5. A graph G = g_{5}(m, n, k, l) (m ⩽ n ⩽ k ⩽ l) belongs to the class E_{1}(3) if and only if (m, n, k, l) has one of the following values:

(1, 1, 4, ˙1), (1, 1, 5, 8), (1, 1, 6, 6).

Proposition 6. A graph G = g_{6}(m, n, k, l, p) (m ⩽ p) belongs to the class E_{1}(3) if and only if (m, n, k, l, p) has one of the following values:

(1, 1, 1, ˙1, ˙1), (1, 2, ˙1, 2, 1), (1, 1, ˙1, 3, 2),
(1, 1, 9, 4, 2), (1, 1, 6, 5, 2), (1, 1, 5, 6, 2),
(1, 1, 4, 12, 2), (1, 1, 3, ˙1, 2), (1, 1, 3, 2, 3),
(1, 1, 2, ˙1, 3), (1, 1, ˙1, 1, 3), (1, 1, 4, 1, 4),
(1, 1, 2, 3, 4), (1, 1, 2, 1, 5), (2, 1, ˙1, 1, 2),
(1, 1, ˙1, ˙1, 1), (1, 3, ˙1, 1, 2).

Proposition 7. A graph G = g_{7}(m, n, k, l, p) (m ⩽ p) belongs to the class E_{1}(3) if and only if (m, n, k, l) has one of the following values:

(1, 1, 1, ˙1, ˙1), (1, 1, ˙1, 1, 3), (1, 1, 3, 1, 4),
(1, 1, 2, 1, 5), (1, 3, 1, ˙1, 1), (1, 4, 1, 9, 1),
(1, 5, 1, 5, 1), (1, 1, 6, ˙1, 1), (1, 1, ˙1, 4, 1),
(1, 1, 7, 47, 1), (1, 1, 8, 13, 1), (1, 1, 9, 9, 1),
(1, 1, 11, 7, 1), (1, 1, 12, 6, 1), (1, 1, 19, 5, 1),
(1, 2, 1, ˙1, 2), (1, 2, 1, 2, 3), (1, ˙1, 2, 1, 2),
(1, 4, 1, 1, 3), (1, 2, 1, 1, 4), (1, 1, 7, 2, 2),
(1, 1, 2, ˙1, 5), (1, 1, 2, 5, 6), (1, 3, 1, 2, 2),
(1, 1, 3, ˙1, 2), (1, 1, 4, 6, 2), (1, 1, 3, 3, 3).

Proposition 8. A graph G = g_{8}(m, n, k, l, p) (m ⩽ n) belongs to the class E_{1}(3) if and only if (m, n, k, l, p) has one of the following values:

(1, 1, 1, 3, ˙1), (1, 1, 1, ˙1, 1), (˙1, ˙1, 1, 1, 1),
(1, ˙1, ˙1, 1, 1), (1, 1, 6, 1, ˙1), (1, 1, 7, 1,114),
(1, 1, 8, 1, 30), (1, 1, 9, 1, 19), (1, 1, 10, 1, 15),
(1, 1, 11, 1, 13), (1, 1, 12, 1, 12), (1, 2, 2, 1, ˙1),
(1, 2, ˙1, 1, 3), (1, 2, 2, 2, 1), (1, 2, 3, 1, 8),
(1, 2, 4, 1, 6), (1, 2, 5, 1, 5), (1, 2, 15, 1, 4),
(1, 3, 1, 2, 1), (1, 3, 1, 1, 12), (1, 3, 2, 1, 4),
(1, 4, 1, 1, 4), (1, 5, ˙1, 1, 2), (1, 5, 1, 1, 3),
(1, 6, 27, 1, 2), (1, 7, 6, 1, 2), (1, 8, 3, 1, 2),
(1, 10, 2, 1, 2), (1, 17, 1, 1, 2), (1, 3, 10, 1, 3),
(2, 2, 1, 1, ˙1), (2, 2, 2, 1, 5), (2, 2, 3, 1, 3),
(2, 3, ˙1, 1, 1), (2, 3, 1, 1, 5), (2, 3, 3, 1, 2),
(2, 4, 17, 1, 1), (2, 5, 10, 1, 1), (2, 6, 7, 1, 1),
(2, 8, 6, 1, 1), (2, 11, 5, 1, 1), (2, 23, 4, 1, 1),
(2, ˙1, 3, 1, 1), (2, 4, 1, 1, 3), (2, 4, 2, 1, 2),
(2, 8, 1, 1, 2), (3, ˙1, 2, 1, 1), (3, 3, 1, 1, 3),
(3, 4, 2, 1, 2), (3, 5, 3, 1, 1), (3, 6, 1, 1, 2),
(4, 14, 2, 1, 1), (5, 5, 1, 1, 2).

Proposition 9. A graph G = g_{9}(m, n, k, l, p) (k ⩽ l ⩽ p) belongs to the class E_{1}(3) if and only if (m, n, k, l, p) has one of the following values:

(1, 1, 1, 1, ˙1), (3, ˙1, 1, 1, 1), (4, 1, 1, 1, 1), (1, 3, 1, 1, 2).

Proposition 10. A graph G = g_{10}(m, n, k, l) (k ⩽ p) belongs to the class E_{1}(3) if and only if (m, n, k, l, p) has one of the following values:

(1, 1, 1, 1, ˙1), (1, ˙1, 1, 1, 1), (1, 1, 1, ˙1, 1),
(1, 5, 1, 1, 2), (1, 2, 1, 1, 3), (1, 3, 1, 2, 1),
(2, 5, 1, 1, 1), (3, 1, 1, 1, 1), (1, 1, 1, 2, 3).

Proposition 11. A graph G = g_{11}(m, n, k, l, p) (m ⩽ n) belongs to the class E_{1}(3) if and only if (m, n, k, l, p) has one of the following values:

(1, ˙1, 1, 1, 1), (1, 1, 1, ˙1, 1), (1, 1, 1, 1, ˙1),

(1, 1, ˙1, 1, 1), (1, 1, 1, 2, 7), (1, 1, 1, 4, 2), (1, 2, 1, 2, 1).

Proposition 12. A graph G = g_{12}(m, n, k, l, p) (l ⩽ p) belongs to the class E_{1}(3) if and only if (m, n, k, l, p) has one of the following values:

(1, 1, ˙1, 1, 1), (1, 1, 1, 1, 2), (1, 2, 3, 1, 1), (1, 3, 1, 1, 1).

Proposition 13. A graph G = g_{13}(m, n, k, l, p) belongs to the class E_{1}(3) if and only if (m, n, k, l, p) has one of the following values:

(1, 1, ˙1, 1, 1), (1, 1, 1, ˙1, 1), (1, 1, 1, 1, ˙1),

(1, 1, 1, 2, 2), (1, 1, 3, 2, 1), (2, 1, 1, 2, 1), (2, 1, 3, 1, 1).

Proposition 14. A graph G = g_{14}(m, n, k, l, p) belongs to the class E_{1}(3) if and only if

(m, n, k, l, p) = (1, 1, ˙1, 1, 1).

Proposition 15. A graph G = g_{15}(m, n, k, l, p) belongs to the class E_{1}(3) if and only if

(m, n, k, l, p) = (1, 1, 1, 1, ˙1).

Proposition 16. A graph G = g_{16}(m, n, k, l, p) (m ⩽ n ⩽ k ⩽ l ⩽ p) belongs to the class E_{1}(3) if and only if

(m, n, k, l, p) = (1, 1, 1, 1, 1).

Proposition 17. A graph G = g_{17}(m, n, k, l, p, q) (m ⩽ q) belongs to the class E_{1}(3) if and only if (m, n, k, l, p, q) has one of the following values:

(1, 1, 1, 1, 3, 1), (1, 1, 1, 2, 1, 1).

Proposition 18. A graph G = g_{18}(m, n, k, l, p, q) belongs to the class E_{1}(3) if and only if (m, n, k, l, p, q) has one of the following values:

(1, 1, 1, 1, 3, ˙1), (1, 1, 2, 1, 1, ˙1), (1, 1, 1, 1, 6, 1),
(1, 1, 1, 2, 2, 1), (1, 1, 1, 1, 4, 2), (1, 1, 3, 1, 1, 3).

Proposition 19. A graph G = g_{19}(m, n, k, l, p, q) belongs to the class E_{1}(3) if and only if

(m, n, k, l, p, q) = (1, 1, 1, 1, 1, 1).

Proposition 20. A graph G = g_{20}(m, n, k, l, p, q) (m ⩽ l) belongs to the class E_{1}(3) if and only if

(m, n, k, l, p, q) = (1, 1, 1, 2, 1, 1).

Proposition 21. A graph G = g_{21}(m, n, k, l, p, q) (p ⩽ q) belongs to the class E_{1}(3) if and only if (m, n, k, l, p, q) has one of the following values:

(1, 4, 1, 1, 1, 1), (1, 1, 3, 1, 1, 1), (1, 1, 1, 2, 1, 1).

Proposition 22. A graph G = g_{22}(m, n, k, l, p, q) belongs to the class E_{1}(3) if and only if

(m, n, k, l, p, q) = (1, 1, 1, 1, 1, 1).

Proposition 23. A graph G = g_{23}(m, n, k, l, p, q) belongs to the class E_{1}(3) if and only if

(m, n, k, l, p, q) = (1, 1, 1, 1, 1, 1).

Proposition 24. A graph G = g_{24}(m, n, k, l, p, q) (p ⩽ q) belongs to the class E_{1}(3) if and only if

(m, n, k, l, p, q) = (1, 1, 1, 1, 1, 4).

Propositions 1–24 and Theorem 1 completely describe the class E_{1}(3).

References

[1] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs-Theory and Applications, revised and enlarged edition, J. A. Barth Verlag, Heidelberg–Leipzig, 1995.

[2] D. Cvetković, M. Petrić, A table of connected graphs on six vertices, Discrete Math. 50 (1984), 37–49

[3] M. Lepović, Some results on the reduced energy of graphs, III, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 2 (1991), 82–88

[4] M. Lepović, Solving some hereditary problems in spectral graph theory, Ph.D. thesis, University of Belgrade, 1991.

[5] A. Torgašev, On infinite graphs with three and four non-zero eigenvalues, Bull. Serb. Acad. Sci. Arts 64 Sci. Math. 11 (1981), 39–48

[6] A. Torgašev, A property of canonical graphs, Publ. Inst. Math. (Beograd)

Prirodno-matematički fakultet (Received 25 02 2004) 34000 Kragujevac, p.p. 60 (Revised 05 05 2005) Serbia and Montenegro

    mmmvl@kg.ac.yu