Bulletin T.CXXXIII de l’Académie serbe des sciences et des arts − 2006 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 31

GRAPHS WITH LEAST EIGENVALUE −2 ATTAINING A CONVEX QUADRATIC UPPER BOUND FOR THE STABILITY NUMBER

D. M. CARDOSO, D. CVETKOVIĆ

(Presented at the 1st Meeting, held on February 24, 2006)

A b s t r a c t. In this paper we study the conditions under which the stability number of line graphs, generalized line graphs and exceptional graphs attains a convex quadratic programming upper bound. In regular graphs this bound is reduced to the well known Hoffman bound. Some vertex subsets inducing subgraphs with regularity properties are analyzed. Based on an observation concerning the Hoffman bound a new construction of regular exceptional graphs is provided.

AMS Mathematics Subject Classification (2000): 05C50

Key Words: graph theory, graph spectra, line graph , quadratic programming, stability number

1. Introduction

The spectrum of a graph is the spectrum of its adjacency matrix.

Graphs with least eigenvalue −2 can be represented by sets of vectors at angles of 60 or 90 degrees via the corresponding Gram matrices. Maximal sets of lines through the origin with such mutual angles are closely related to the root systems known from the theory of Lie algebras. Using such a geometrical characterization one can show [4, 12] that graphs in question are either generalized line graphs (representable in the root system D_{n} for some n) or exceptional graphs (representable in the exceptional root system E_{8}).

We shall study the following problem.

Problem. For which graphs with least eigenvalue greater than or equal to −2 the Hoffman upper bound (4) (and a convex quadratic programming generalization (2)) for the stability number is attained ?

The rest of the paper is organized as follows.

Section 2 contains some definitions related to graphs with least eigenvalue greater than or equal to −2 while in Section 3 the bound is described. In Section 4 some vertex subsets inducing subgraphs with regularity properties are analyzed. In Section 5 we describe the solution for line graphs. This result is extended to generalized line graphs in Section 6. Exceptional graphs are treated in Section 7. Based on an observation in Section 7 concerning the Hoffman bound a new construction of regular exceptional graphs is given in Section 8.

2. Some basic notions

Let G be a simple graph with n vertices. We write V (G) for the vertex set of G, and E(G) for the edge set of G. If X is a subset of V (G), the subgraph of G induced by X is denoted by G[X]. As usual, K_{n}, C_{n} and P_{n} denote, respectively, the complete graph, the cycle and the path on n vertices. Further, K_{m,n} denotes the complete bipartite graph on m + n vertices. The cocktail-party graph CP (n) is the unique regular graph with 2n vertices of degree 2n − 2; it is obtained from K_{2n} by deleting n mutually non-adjacent edges. The union of (disjoint) graphs G and H is denoted by G ∪ H, while mG denotes the union of m disjoint copies of G.

The characteristic polynomial det(xI − A) of the adjacency matrix A of G is called the characteristic polynomial of G and denoted by P_{G}(x). The eigenvalues of A (i.e., the zeros of det(xI − A)) and the spectrum of A (which consists of the n eigenvalues) are also called the eigenvalues and the spectrum of G, respectively. The eigenvalues of G are reals λ_{1}, λ_{2}, …, λ_{n} and we shall assume that λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n}.

Graphs with least eigenvalue −2 attaining a convex quadratic... 43

A pendant double edge is called a petal. A blossom B_{n} consists of n (n ≥ 0) petals attached at a single vertex. An empty blossom B_{0} has no petals and is reduced to the trivial graph K_{1}. A graph in which a blossom (possibly empty) is attached to each vertex is called a graph with blossoms or a B–graph. The set of B–graphs includes as a subset the set of (undirected) graphs without loops or multiple edges. A graph G is a generalized line graph (GLG) if G = L(H) is the line graph of a B–graph H called the root graph of G.

The line graph L(H) of any graph H is defined as follows. The vertices of L(H) are the edges of H and two vertices of L(H) are adjacent whenever the corresponding edges of H have exactly one vertex of H in common.

We have L(B_{n}) = CP (n). A GLG is called a line graph if there exists a B–graph H with no petals such that G = L(H) while in the opposite case G is a proper generalized line graph.

Furthermore (see [9]), a GLG may be denoted by L(H; a_{1}, …, a_{n}), where H is a connected graph, V (H) = {1, …, n} with n > 1, a_{1}, …, a_{n} are nonnegative integers, and its root graph is the B–graph Ĥ (and then L(Ĥ) = L(H; a_{1}, …, a_{n})) obtained from H by attaching to each vertex i the blossom B_{a_{i}} for i = 1, …, n.

An exceptional graph is a connected graph with least eigenvalue greater than or equal to −2 which is not a generalized line graph.

Let L be the set of graphs whose least eigenvalue is greater than or equal to −2. A graph is called an L–graph if its least eigenvalue is greater than or equal to −2.

For other definitions and basic results the reader is referred to books:

[10] for graph spectra in general and [12] for L–graphs.

3. The convex quadratic upper bound for the stability number

If G has at least one edge, considering the convex quadratic program, presented in [15],

υ(G) = max_{x≥0} 2ê^{T} x − x^{T} (\frac{A}{−λ_{n}} + I)x,  (1)

where A is the adjacency matrix of G, λ_{n} the minimum eigenvalue of G, ê denotes the all ones vector and I the identity matrix of order |V (G)|, then we have the following result:

Theorem 3.1 [15] Let G be a graph with at least one edge. Then

α(G) ≤ υ(G).  (2)

Furthermore, υ(G) = α(G) if and only if for a maximum stable set S (and then for all)

−λ_{n} ≤ min{|N_{G}(v) ∩ S| : v ∉ S},  (3)

where N_{G}(v) denotes the neighborhood of the vertex v (that is, the set of vertices adjacent to v).

Now, we introduce the following slight more general necessary and sufficient condition:

Theorem 3.2 Given a graph G with at least one edge, we have υ(G) = α(G) if and only if there exists a stable set S for which (3) holds.

P r o o f. If υ(G) = α(G) then Theorem 3.1 implies the result. Conversely, let us assume that there exists a stable set S for which (3) holds. Then the characteristic vector of S, x̄ = x(S) (that is, the vector x̄ such that x̄_{i} = 1 if i ∈ S, and x̄_{i} = 0 otherwise) and the vector y such that

y_{i} = \{ \begin{matrix}0, & if i ∈ S; \\ |N_{G}(i) ∩ S| − λ_{n}, & otherwise, \end{matrix}

fulfill the Karush-Khun-Tucker conditions for the convex quadratic programming problem (1): y^{T} x̄ = 0 and Ax̄ = −λ_{n}(ê − x̄) + y. Therefore, x̄ is an optimal solution for (1) and then α(G) ≤ υ(G) = |S| ≤ α(G). □

A graph G such that υ(G) = α(G) was called in [5] graph with convex-QP stability number (where QP stands for quadratic programming). When G is a regular graph of order n, as firstly observed in [15], υ(G) = n\frac{−λ_{n}}{λ_{1}−λ_{n}} which is precisely the very popular upper bound on the stability number of regular graphs obtained by Hoffman (unpublished) and presented by Lovász in [14] by the inequality

α(G) ≤ n\frac{−λ_{n}}{λ_{1} − λ_{n}} .  (4)

Considering S as a vertex subset of a p-regular connected graph G, the Hoffman bound can be obtained from the inequalities

|S|\frac{p − λ_{n}}{n} + λ_{n} ≤ d̄_{G[S]} ≤ |S|\frac{p − λ_{2}}{n} + λ_{2},  (5)

where d̄_{G[S]} is the average vertex degree of the subgraph of G induced by S. In fact, if G is p-regular, from these inequalities, it follows that

n\frac{d̄_{G[S]} − λ_{2}(A_{G})}{p − λ_{2}(A_{G})} ≤ |S| ≤ n\frac{d̄_{G[S]} − λ_{min}(A_{G})}{p − λ_{min}(A_{G})}.  (6)

Therefore, if S induces a maximum stable set, then the Hoffman inequality (4) is obtained.

There are many papers related to the Hoffman bound and, in particular, to the case when the bound is attained. It would be difficult to survey all of them, partly because there exists a confusion in some papers concerning priorities. Here and in the next section we shall mention some relevant references not pretending to give a complete list.

The inequality (5) was proved in [2] and presented at the V Hungarian Colloquium on Combinatorics, Keszthelly 1976. This communication resulted in the paper [3] published in the proceedings of this colloquium. In fact, [3] represents a summary of results of [2]. Almost the whole content of [2] was included into the book [12] and, in particular, the inequalities (5) with the original proof as Theorem 1.2.25. Some related bibliographical data can be found in [10], p. 115. Among other things it was noted there that the Hoffman bound is a special case of the first inequality in (5).

Note that the thesis [16] mentions correctly that (5) appears in [3] without a proof but, instead of saying that the proof is contained in [2], says that the proof is probably given in a paper by W.Haemers.

4. Some remarks on graphs with (k, τ)-regular sets

Let us consider the concept of (k, τ)-regular set, introduced in [7], which is a vertex subset S of a graph G, inducing a k-regular subgraph such that every vertex out of S has τ neighbors in S, that is, for any v ∈ V (G) we have

|N_{G}(v) ∩ S| = \{ \begin{matrix}k, & if v ∈ S; \\ τ, & otherwise. \end{matrix}

For instance, considering the Petersen graph depicted in Figure 1, the following (k, τ)-regular sets are obtained.

• The set S_{1} = {1, 2, 3, 4} is (0, 2)−regular.

• The set S_{2} = {5, 6, 7, 8, 9, 10} is (1, 3)−regular.

• The set S_{3} = {1, 2, 5, 7, 8} is (2, 1)−regular.

[figure: 3; 4; 9; 10; 6; 7; 8; 5; 1; 2]

Figure 1. The Petersen graph

According to Godsil and Royle (see [13], Lemma 9.6.2), we may conclude that if the Hoffman bound is attained for a regular graph G, then G contains a (0, τ)-regular set such that τ = −λ_{n}. Conversely, if a p-regular graph G contains a (0, τ)-regular set S, with τ = −λ_{n}, then

p|S| = (n − |S|)τ ⇔ |S| = n\frac{τ}{p + τ} = n\frac{−λ_{n}}{λ_{1} − λ_{n}} .

Therefore, since α(G) ≤ n\frac{−λ_{n}}{λ_{1}−λ_{n}} = |S| ≤ α(G), it follows that α(G) = n\frac{−λ_{n}}{λ_{1}−λ_{n}}. As immediate consequence, we have the following necessary and sufficient condition for the convex quadratic bound (1) be tight (when applied to regular graphs).

Theorem 4.1 Let G be a regular graph with at least one edge. Then α(G) = υ(G) if and only if there exists a (0, τ)-regular set S ⊂ V (G), with τ = −λ_{n}. Furthermore, S is a maximum stable set and then every maximum stable set is (0, τ)-regular.

It should be noted that, according to Theorem 3.2, if a graph G (regular or non-regular) has a (0, τ)-regular set, with τ = −λ_{n}, then α(G) = υ(G).

Regarding the existence of (k, τ)-regular sets in regular graphs, we have the following necessary and sufficient condition, proved in [17] (using a different terminology).

Theorem 4.2 [17] A p-regular graph has a (k, τ)-regular set S, with k < p, if and only if k − τ is an eigenvalue and x − \frac{τ}{p+τ−k} ê, where x = x(S) is the characteristic vector of S, is a (k − τ)-eigenvector.

A subgraph of a graph G induced by a (k, τ)-regular set is called in [17] an eigengraph of G. Using a distinct approach, the following equivalent result (here presented as a corollary of Theorem 4.2) was rediscovered in [8].

Corollary 4.1 Let G be a p-regular graph and S ⊂ V (G). There are k ∈ ℕ ∪ {0} and τ ∈ ℕ, with k − τ = λ, such that S is (k, τ)-regular if and only if ∃u ∈ Ker(A_{G} − λI) such that

u_{i} = \{ \begin{matrix}1 − \frac{|V (G)|}{|S|}, & if i ∈ S; \\ 1, & otherwise, \end{matrix}

where Ker(C) denotes the null space of matrix C.

For the particular case of (0, τ)-regular sets, a similar result was obtained in [6], using the concept of τ-regular-stable graph introduced in [1] (which is a graph G with a maximum independent vertex set S, such that for every vertex v ∉ S, |N_{G}(v)∩S| = τ). According to [6], if the graph G is τ-regular-stable, with τ > 0, then there exists a maximum stable set S such that its characteristic vector is a solution of the linear system

A_{G}x = τ(ê − x).  (7)

On the other hand, if τ = −λ_{n} and the system (7) has a solution x̄ ∈ {0, 1}^{|V (G)|}, then x̄ is the characteristic vector of a maximum stable set. The first implication is obvious and the second follows from the fact that if x̄ ∈ {0, 1}^{|V (G)|} is a solution of (7), then x̄^{T} A_{G}x̄ = 0, which is equivalent to say that x̄ is the characteristic vector of a stable set S of G. Hence, since τ = −λ_{n}, x̄ is the optimal solution of the convex quadratic programming problem (1) and then |S| = υ(G) = α(G).

Now, a maximum independent vertex set defining a τ-regular-stable graph is designated (0, τ)-regular.

As immediate consequence, assuming that the p-regular graph G includes a (0, τ)-regular set, then its characteristic vector is a solution of the linear system (7) and thus, adding −\frac{τ}{p+τ} A_{G}ê = −\frac{pτ}{p+τ} ê to both sides of (7), it follows that

A_{G}(x − \frac{τ}{p + τ} ê) = −τ(x − \frac{τ}{p + τ} ê).

Conversely, if û = x − \frac{τ}{p+τ} ê, where x ∈ \{0, 1\}^{|V (G)|}, is a −τ-eigenvector, then

A_{G}(x − \frac{τ}{p + τ} ê) = −τ(x − \frac{τ}{p + τ} ê) ⇔ A_{G}x = −τ(x − ê),

and thus x^{T} A_{G}x = 0, that is, x is the characteristic vector of an independent set of G (which then is maximum).

Therefore, if G is a p-regular graph and τ = −λ_{n}, then G has a (0, τ)- regular set (or, equivalently, the Hoffman bound is attained) if and only if there exists x ∈ \{0, 1\}^{|V (G)|}, such that x− \frac{τ}{p+τ} ê is a λ_{n}-eigenvector. Furthermore, x is the characteristic vector of a maximum independent set. Part of this result was independently obtained in [16].

Now, more generally, we have the following slightly different version of Theorem 4.2.

Theorem 4.3 A p-regular graph G has a (k, τ)-regular set, with k < p, if and only if k − τ is an eigenvalue and there exists x ∈ {0, 1}^{|V (G)|}, such that x− \frac{τ}{p+τ−k} ê is a (k−τ)-eigenvector. Furthermore, x is the characteristic vector of a (k, τ)-regular set.

P r o o f. Let G be a p-regular graph. If S ⊂ V (G) is a (k, τ)-regular set, with k < p, then the characteristic vector of S, x = x(S), is a solution of the linear system

A_{G}x = (k − τ)(x − ê) + kê.  (8)

Adding \frac{−τ}{p+τ−k}A_{G}ê = \frac{−τp}{p+τ−k} ê to both sides of (8) it follows that

A_{G}(x − \frac{τ}{p + τ − k} ê) = (k − τ)(x − \frac{τ}{p + τ − k} ê).

Conversely, if x ∈ \{0, 1\}^{|V (G)|} is such that x− \frac{τ}{p+τ−k} ê is a (k−τ)-eigenvector, then x is a solution of the linear system (8). Denoting by S the vertex set defined by the characteristic vector x, it follows that ∀v ∈ V (G)

|N_{G}(v) ∩ S| = (A_{G}x)_{v} = (k − τ)(x_{v} − 1) + k = \{ \begin{matrix}k, & if v ∈ S; \\ τ, & otherwise. \end{matrix}

□

5. Line graphs

A matching is a set of mutually non-adjacent edges and a perfect matching of a graph H is a matching M such that each vertex v ∈ V (H) is incident to an edge of M. Since a graph has a perfect matching if and only if each component has a perfect matching and the optimal value of the convex quadratic programming problem (1) is also the sum of the optimal values obtained for each component, we may rewrite the theorem deduced in [5] in the following form:

Theorem 5.1 [5] A graph H with at least one edge, such that each component of H is neither a star nor a triangle, has a perfect matching if and only if the line graph L(H) has convex-QP stability number.

Therefore, the stability number of the line graph L(H) of a graph H (of order n > 2, where each component is neither a star nor a triangle) attains the upper bound υ(L(H)) if and only if H has a perfect matching. Notice that a matching of H corresponds to a stable set of L(H) and then the stability number of L(H) is the cardinality of a maximum matching of H.

The content of Theorem 5.1 is trivial for regular graphs. In this case the bound (1) is reduced to Hoffman’s bound (4). If G = L(H) is regular, then H is either regular or semi-regular bipartite.

If H is regular of degree r and has n vertices and if G has least eigenvalue −2, then υ(G) = n/2. Of course, we have α(G) = n/2 if and only if H has a perfect matching. The only regular connected graphs with least eigenvalue greater than −2 are complete graphs and odd cycles (cf.,e.g.,[12], Corollary 2.3.22). In the case of odd cycles we have G = L(H) = H = C_{2k+1} for some k. The eigenvalues of G are 2 cos \frac{2π}{2k+1}i, i = 0, 1, …, 2k, and we readily get υ(G) = n\frac{cos β}{1+cos β} with β = \frac{π}{2k+1}. Since G has no perfect matching, the bound is not attained by Theorem 5.1 but α(G) = k is very close to υ(G). In the case of complete graphs the bound is attained although complete graphs are excluded from Theorem 5.1

If H is semi-regular bipartite with parameters n_{1}, n_{2}, d_{1}, d_{2}, assuming that d_{1}, d_{2} are both greater than 1 (otherwise, the least eigenvalue of G is −1), the largest eigenvalue of G is d_{1} + d_{2} − 2 and we have υ(G) = \frac{2n_{1}d_{1}}{d_{1}+d_{2}} . However, if H has a perfect matching, we have n_{1} = n_{2} and then necessarily d_{1} = d_{2}. This reduces our case to the previous one and we have again υ(G) = n_{1} = n/2.

Taking into account that a graph H has a perfect matching if and only if L(H) has a (0, 2)-regular set, we have the following corollary:

Corollary 5.1 Let H be a graph with at least one edge, such that each component is neither a star nor a triangle. Then G = L(H) has convex-QP stability number if and only if G has a (0, 2)-regular set.

P r o o f. According to the above, L(H) has as a (0, 2)-regular set if and only if H has a perfect matching. (Note that if V (L(H)) is a set of isolated vertices then it is (0, k)-regular for every k ∈ ℕ). Furthermore, according to Theorem 5.1, H has a perfect matching if and only if the line graph L(H) has convex-QP stability number. □

Combining this corollary with Theorem 4.2, we have a new necessary and sufficient condition for the particular case of regular line graphs.

Corollary 5.2 Let G = L(H) be a p-regular graph with p > 2. Then G has convex-QP stability number if and only if −2 is an eigenvalue of G with an eigenvector (p + 2)x̄ − 2ê, where x̄ = x(S) is the characteristic vector of a (0, 2)-regular set S ⊂ V (G) and ê is the all-one vector.

P r o o f. Since H is p-regular, with p > 2, it follows that H has at least one edge and each component is neither a star nor a triangle. Therefore, applying Corollary 5.1 first and then Theorem 4.2, the result follows. □

6. Generalized line graphs

Taking into account that a GLG is an L–graph, that is, a graph for which λ_{n} ≥ −2, and noting that if the GLG is not complete then −2 ≤ λ_{n} < −1, we have the following result:

Theorem 6.1 Let G = L(H, a_{1}, …, a_{n}) be a generalized line graph different from K_{n}. Let V (H) = V_{1} ∪ V_{2}, where V_{1} = {i ∈ V (H) : a_{i} > 0} and V_{2} = V (H) \ V_{1}. If V_{2} = ∅ or H[V_{2}] has no edges then υ(G) = α(G), otherwise this equality holds if and only if the subgraph H[V_{2}], after deleting its isolated vertices (if they exist), has a perfect matching.

P r o o f. Suppose that υ(G) = α(G). Then the characteristic vector of a maximum stable set S ⊆ V (G), x̄ = x(S), is an optimal solution for the convex quadratic program (1). By the Karush-Kuhn-Tucker conditions, there exists y ≥ 0 such that y^{T} x̄ = 0 and Ax̄ = −λ_{n}(ê − x̄) + y or, equivalently, for each v_{e} ∈ V (G),

(Ax̄)_{v_{e}} = |N_{G}(v_{e}) ∩ S| = \{ \begin{matrix}0, & if v_{e} ∈ S; \\ −λ_{n} + y_{v_{e}}, & if v_{e} ∉ S, \end{matrix}  (9)

where A is the adjacency matrix of G. It should be noted that the vertices of the maximum stable set S can be partitioned into the subsets S_{1} and S_{2}, such that the vertices in S_{1} correspond to edges of petals (the pairs of edges of petals just one chosen from the blossom B_{a_{i}} attached to each vertex i ∈ V_{1}) and the vertices in S_{2} correspond to edges of a matching M in H[V_{2}], if E(H[V_{2}]) ≠ ∅.

Let us suppose that E(H[V_{2}]) ≠ ∅. Then, for each vertex v_{e} ∈ V (G) \ S corresponding to an edge e ∈ E(H[V_{2}])\M, from (9), we may conclude that

|N_{G}(v_{e}) ∩ S| = −λ_{n} + y_{v_{e}} ⇒ |N_{G}(v_{e}) ∩ S| > 1,

and then e has two adjacent edges in M (since it is not possible to be adjacent to more than two). Therefore, M is a perfect matching for H[V_{2}].

Conversely, let us suppose that H[V_{2}] without isolated vertices (if they exist) has a perfect matching M. Consider the vertex subset S = S_{1} ∪ S_{2}, where the vertices of S_{1} correspond to the edges of petals just one chosen from the blossom B_{a_{i}} attached to each vertex i ∈ V_{1}, and the vertices of S_{2} correspond to the edges of the perfect matching M ⊆ E(H[V_{2}]), if E(H[V_{2}]) ≠ ∅ or S_{2} = ∅, otherwise. Let x̄ = x(S) be the characteristic vector of S. Then, denoting by v_{e} the vertex of V (G) corresponding to the edge e ∈ E(Ĥ), for y such that

y_{v_{e}} = \{ \begin{matrix}0, & if v_{e} ∈ S; \\ 2 + λ_{n}, & if v_{e} ∉ S, and e belongs to a petal; \\ 4 + λ_{n}, & if v_{e} ∉ S, and e ∈ E(H[V_{1}]); \\ 2 + λ_{n}, & if v_{e} ∉ S, S_{2} = ∅, and e=xy is such that x ∈ V_{1} and y ∈ V_{2}; \\ 3 + λ_{n}, & if v_{e} ∉ S, S_{2} ≠ ∅, and e=xy is such that x ∈ V_{1} and y ∈ V_{2}; \\ 2 + λ_{n}, & if v_{e} ∉ S, S_{2} ≠ ∅, and e ∈ E(H[V_{2}]) \ M, \end{matrix}

it is immediate that y ≥ 0 and is such that jointly with x̄ fulfill the Karush-Kuhn-Tucker conditions y^{T} x̄ = 0 and (9). Therefore, x̄ is an optimal solution for the convex quadratic programming problem (1) and, since α(G) ≤ υ(G) = |S| ≤ α(G), it follows that α(G) = υ(G). □

The case of regular graphs is again easy. By Proposition 1.1.9 of [12] a regular connected generalized line graph is either a line graph or a cocktail party graph. Regular line graphs are covered by Theorem 4.1 and by the comment after that theorem. The cocktail party graph G = CP (k) has distinct eigenvalues 2k − 2, 0, −2 and we get υ(G) = α(G)(= 2). The same conclusion also follows from Theorem 5.1.

Note that the bound is attained if each vertex of H has at least one petal attached. In this case we have υ(G) = α(G) = 2n.

7. Exceptional graphs

The bound is attained for almost all regular exceptional graphs. There are 187 such graphs. The set of these graphs is partitioned into three subsets called layers. By definition (cf., [12], p.91), a regular exceptional graph of degree r with n vertices belongs to first, second, third layer if it satisfies the relations n = 2(r + 2), n = \frac{3}{2}(r + 2), n = \frac{4}{3}(r + 2), respectively.

The graphs were originally found in [2] and they are described in Chapter 4 and Tables A3 and A4 of the book [12].

From the layer defining relations it follows that the Hoffman bound is equal to

4 for graphs in the first layer (163 graphs including the Petersen graph), 3 for graphs in the second layer (21 graphs), 8/3 for graphs in the third layer (3 graphs). The data from the mentioned tables show that α = 4, 3, 2 for these layers,

respectively.

Hence, the bound is attained for graphs in the first and in the second layer. It is attained in a weaker sense even in the third layer (α is equal to the largest integer satisfying the Hoffman inequality).

For non-regular exceptional graphs we do not have a general solution but we provide some examples.

Below is a table with the values υ(G) and α(G) (obtained using MatLab) for the 20 minimal exceptional graphs F_{1}, F_{2}, …, F_{20} as given at p. 198 of the book [12].

\begin{matrix}Graph & υ(G) & α(G) \\ F_{1} & 3.6357 & 3 \\ F_{2} & 3.2361 & 3 \\ F_{3} & 3.6302 & 3 \\ F_{4} & 3.3111 & 3 \\ F_{5} & 3.6222 & 3 \\ F_{6} & 3.3568 & 3 \\ F_{7} & 2.5670 & 2 \\ F_{8} & 3.2998 & 3 \\ F_{9} & 3.3272 & 3 \\ F_{10} & 2.5724 & 2 \\ F_{11} & 3 & 3 \\ F_{12} & 2.6099 & 2 \\ F_{13} & 3.3012 & 3 \\ F_{14} & 2.2361 & 2 \\ F_{15} & 3 & 3 \\ F_{16} & 2.5336 & 2 \\ F_{17} & 2.5858 & 2 \\ F_{18} & 2.4140 & 2 \\ F_{19} & 2.2674 & 2 \\ F_{20} & 2.2866 & 2 \end{matrix}

8. A recursive construction of regular exceptional graphs

The fact that the Hoffman bound is attained by all regular exceptional graphs in the first and in the second layer enables a recursive construction of these graphs. We shall elaborate here the case of the first layer.

Let G be a regular exceptional graph of degree r with n vertices which belongs to the first layer. We have n = 2(r +2). Let S be a maximum stable set in G which means |S| = 4. By Theorem 4.1, S is a (0, 2)-regular set of G. Moreover, the graph G′ = G − S is regular of degree r′ = r − 2 and has n′ = n−4 vertices. G′ is an L-graph and if it is exceptional it belongs to the first layer since n′ = 2(r′ + 2). In the other case G′ is a line graph or/and a disconnected graph. Of course, G′ cannot be a cocktail party graph since in this case it should be n′ = r′ + 2 which is not true. If G′ is disconnected then again it is a line graph what follows by enumeration of possible cases (see below).

Smallest regular exceptional graphs in the first layer are the five graphs Z_{1}, Z_{2}, …, Z_{5} of Fig. 1 on p. 218 of [12]. For such a graph G we have n = 10 and r = 3. For the reduced graph G′ we have n′ = 6 and r′ = 1. Hence, G′ = 3K_{2} and this is a line graph. It follows that all graphs Z_{1}, Z_{2}, …, Z_{5} can be obtained by adding edges between the six vertices of 3K_{2} and four vertices of 4K_{1} in all possible ways so that the resulting graph is regular of degree 3.

In the next case we have n = 12 and r = 4. Since n′ = 8 and r′ = 2, the graph G′ is one of the following three graphs C_{8}, 2C_{4}, C_{5} ∪ C_{3}.

If n = 14 and r = 5, the set of possible graphs G′ (n′ = 10, r′ = 3) consists of all regular line graphs of degree 3 on 10 vertices and of graphs Z_{1}, Z_{2}, …, Z_{5}.

In general, for n′ = 6, 8, …, 24 the graph G′ belongs to the set of regular L-graphs of degree r′ = n′/2 − 2. All regular exceptional graphs G in the first layer can be constructed by extending graphs G′ with additional four vertices in the way implied by the above considerations.

The extension of a reduced graph G′ by the set S which produces the graph G will be called an S-extension. Let us describe S-extensions in some detail.

Let 1,2,3,4 be the vertices of S. Each vertex of G′ should become adjacent to exactly two vertices of S. Let us define an r-regular multigraph M(S) having the set S as the vertex set. If a vertex v of G′ becomes adjacent to vertices x, y of S, then there is an edge labelled v between x and y in M(S). In this way, the vertices of G′ subdivide the edges of M(S). There are six 2-element subsets of S. Constructing G from G′ by an S-extension means, in fact, to partition the vertex set of G′ into six subsets which, in turn, should be assigned to 2-element subsets of S in such a way that M(S) is regular of degree r. However, the resulting graph G need not to be an L-graph which should be checked in actual constructions.

Let us consider the set L of regular L-graphs with even number n of vertices of degree r = n/2 − 2 where 6 ≤ n ≤ 28. For any G, H ∈ L consider the relation: H ⪰_{S} G if and only if ”H can be obtained from G by a finite sequence of zero ore more S-extensions”. This relation is a partial order relation in L and then (L, ⪰_{S}) is a partially ordered set (poset). Our observations can be condensed in the following form.

Theorem 8.1 Regular exceptional graphs are not minimal elements of the poset (L, ⪰_{S}).

It would be interesting to study the structure of L.

Acknowledgements. The first author’s work was supported by Centre for Research in Optimization and Control (CEOC) from the ”Fundação para a Ciência e a Tecnologia” FCT, cofinanced by the European Community Fund FEDER. The second author appreciates the support by the Serbian Ministry for Science and Environmental Protection, Grant 144015G.

REFERENCES

[1] R. B a r b o s a, D. M. C a r d o s o, On regular stable graphs, Ars-Combinatoria, 70(2004), 149–159.

[2] F. C. B u s s e m a k e r, D. C v e t k o v i ć, J. S e i d e l, Graphs related to exceptional root systems, T.H. - Report 76-WSK-05, Technological University Eindhoven, 1976, 1–91.

[3] F. C. B u s s e m a k e r, D. C v e t k o v i ć, J. S e i d e l, Graphs related to exceptional root systems. In: Combinatorics, Proc. V Hungarian Colloquium on Combinatorics, Keszthelly 1976, (Coll. Mat. Soc. J. Bolyai 18, ed. A. Hajnal and V. Sós), North-Holland, Amsterdam-Oxford-New York, 1978, Vol. I, 185–191.

[4] P. J. C a m e r o n, J. M. G o e t h a l s, J. J. S e i d e l, E. E. S h u l t, Line graphs, root systems, and elliptic geometry, J. Algebra, 43(1976), 305–327.

[5] D. M. C a r d o s o, Convex quadratic programming approach to the maximum matching problem, J. Global Optimization, 21(2001), 91–106.

[6] D. M. C a r d o s o, Graphs with stability number equal to optimal value of a convex quadratic program, Matemática Contemporânea (Sociedade Brasileira de Matemática), 25(2003), 9–24.

[7] D. M. C a r d o s o, P. R a m a, Equitable bipartitions of graphs and related results, Journal of Mathematical Sciences, 120(1) (2004), 869–880.

[8] D. M. Cardoso, C. Delorme, P. Rama, Eingenvectors and eigenvalues of graphs with regularity constraints. Research Report, Cadernos de Matemática, CM04-I09, Universidade de Aveiro (March, 2004).

[9] D. C v e t k o v i ć, M. D o o b, S. S i m i ć, Generalized line graphs, J. Graph Theory, 5(1981), No. 4, 385-399.

[10] D. C v e t k o v i ć, M. D o o b, H. S a c h s, Spectra of Graphs, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg - Leipzig, 1995.

[11] D. C v e t k o v i ć, P. R o w l i n s o n, S. S i m i ć, Graphs with least eigenvalue −2: the star complement technique, J. Algebraic Combinatorics, 14(2001), 5–16.

[12] D. C v e t k o v i ć, P. R o w l i n s o n, S. S i m i ć, Spectral Generalizations of Line Graphs, On Graphs with Least Eigenvalue −2, Cambridge University Press, Cambridge, 2004.

[13] C. D. G o d s i l, G. R o y l e, Algebraic Graph Theory. Springer-Verlag, New York (2001).

[14] L. L o v á s z, On the Shannon capacity of a graph. IEEE Transactions on Information Theory 25(2) (1979), 1–7.

[15] C. J. L u z, An upper bound on the independence number of a graph computable in polynomial time, Operations Research Letters, 18(1995), 139–145.

[16] M. W. N e w m a n Indpendent Sets and Eigenspaces, Ph.D. thesis, University of Waterloo (2004).

[17] D. M. T h o m p s o n, Eigengraphs: constructing strongly regular graphs with block designs. Utilitas Math., 20(1981), 83-115.

Department of Mathematics University of Aveiro 3810-193, Aveiro Portugal E-mail: dcardoso@mat.ua.pt Faculty of Electrical Engineering, University of Belgrade, P.O.Box 35–54, 11120 Belgrade, Serbia E-mail: ecvetkod@etf.bg.ac.yu