Also available at http://amc.imfm.si
ARS MATHEMATICA CONTEMPORANEA 1 (2008) 81–98
On Graphs with the Smallest Eigenvalue at Least
−1−
√
2, part I
Tetsuji Taniguchi
Graduate School of Mathematics, Kyushu University, Fukuoka 812-81, Japan
Received 26 September 2007, accepted 29 April 2008, published online 31 July 2008
Abstract
There are many results on graphs with the smallest eigenvalue at least−2. As a next step,
A. J. Hoffman proposed to study graphs with the smallest eigenvalue at least −1 −
√
2. In
order to deal with such graphs, R. Woo and A. Neumaier introduced the concept of a Hoffman
graph, and defined a new generalization of line graphs which depends on a family of Hoffman
graphs. They proved a theorem analogous to Hoffman’s, using a particular family consisting
of four isomorphism classes.
In this paper, we deal with a generalization based on a family H smaller than the one
which they dealt with, yet including generalized line graphs in the sense of Hoffman. The
main result is that the cover of an H -line graph with at least 8 vertices is unique.
Keywords: Generalized line graph, Spectrum.
Math. Subj. Class.: 05C50
1 Introduction
In [1], P. J. Cameron, J. M. Goethals, J. J. Seidel, and E. E. Shult have shown that graphs with
the smallest eigenvalue at least −2 are represented by a subset of the root system An, Dn or
E8. A graph represented by a subset of An is the line graph of a bipartite graph. A graph
represented by a subset of Dn is a generalized line graph. A graph represented by a subset
of E8 has at most 36 vertices, and its maximum degree is at most 28. A graph is said to be
exceptional if it is connected, has the smallest eigenvalue at least−2, and is not a generalized
line graph. Such graphs are represented by a subset of E8, hence the number of exceptional
graphs is finite. The 473 maximal exceptional graphs have been constructed theoretically in
[3] (although first found by computer).
Let λmin(G) be the smallest eigenvalue of a graphG. Let Λ1 be the set of all real numbers
λ such that λ = λmin(G) for some graphG. Let δ(G) denote the minimum degree of a graph
G. In [6], A. J. Hoffman has shown the following theorem:
E-mail address: tetsuzit@math.kyushu-u.ac.jp (Tetsuji Taniguchi)
Copyright c© 2008 DMFA – založništvo
82 Ars Mathematica Contemporanea 1 (2008) 81–98
Theorem 1 (A. J. Hoffman). There exists an integer valued function f , defined on the inter-
section of Λ1 with the half-open interval (−1−
√
2, −1], such that
(1) if G is a connected graph with −2 < λmin(G) ≤ −1, δ(G) ≥ f(λmin(G)), then G is a
clique and λmin(G) = −1;
(2) if G is a connected graph with −1 −
√
2 < λmin(G) ≤ −2, δ(G) ≥ f(λmin(G)), then
G is a generalized line graph and λmin(G) = −2.
Obviously, we are interested in making the values of the function f as small as possible.
Since λmin(G) ≤ −1 if G has at least one edge, and λmin(G) = −1 if and only if G is a
clique, we may take f(−1) = 1. Since an exceptional graph has the maximum degree at most
28 as mentioned above, if a graph has the smallest eigenvalue at least −2 and the maximum
degree at least 29, then it is a generalized line graph. Hence we may take f(−2) = 29. In
order to state the extension of Theorem 1.1 by Woo and Neumaier [8], we need to introduce
several concepts.
Definition 2. A Hoffman graph is a graphH with vertex labeling V (H)→ {s, f}, satisfying
the following conditions:
1. every vertex with label f is adjacent to at least one vertex with label s;
2. vertices with label f are pairwise non-adjacent.
We call a vertex with label s a slim vertex, and a vertex with label f a fat vertex. We denote
by Vs(H) (Vf (H)) the set of slim (fat) vertices of H . An ordinary graph without labeling
can be regarded as a Hoffman graph without fat vertex. Such a graph is called a slim graph.
The subgraph of a Hoffman graphH induced on Vs(H) is called the slim subgraph ofH . We
draw Hoffman graphs by depicting vertices as large (small) black dots if they are fat (slim).
We denote by [H] the isomorphism class of Hoffman graphs containing H . In the fol-
lowing, all graphs considered are Hoffman graphs and all subgraphs considered are induced
subgraphs.
Definition 3. Let H be a Hoffman graph, and let Hi (i = 1, 2, . . . , n) be a family of sub-
graphs of H . The graph H is said to be the sum of Hi (i = 1, 2, . . . , n), denoted
H =
n⊎
i=1
Hi, (1)
if the following conditions are satisfied:
(i) V (H) =
⋃n
i=1 V (H
i);
(ii) Vs(Hi) ∩ Vs(Hj) = ∅ if i 6= j;
(iii) if x ∈ Vs(Hi) and y ∈ Vf (H) are adjacent, then y ∈ V (Hi);
(iv) if x ∈ Vs(Hi), y ∈ Vs(Hj) and i 6= j, then x and y have at most one common fat
neighbour, and they have one if and only if they are adjacent.
One can show easily that the sum defined above is associative, in the sense that one of
H = H1 ]H2 ]H3, H = (H1 ]H2) ]H3 implies the other.
T. Taniguchi: On Graphs with the Smallest Eigenvalue at Least −1−
√
2, part I 83
Example 4. The smallest fat Hoffman graph is the graph H1 consisting of two adjacent
vertices, one of which is slim and the other fat. Let H be a connected Hoffman graph which
is the sum (1), where Hi ∼= H1 for all i = 1, 2, . . . , n. Then the slim subgraph of H is the
complete graph on n vertices.
Example 5. Let H2 be the Hoffman graph consisting of two non-adjacent fat vertices and
one slim vertex, where both fat vertices are adjacent to the slim vertex. Let H be a connected
Hoffman graph which is the sum (1), where Hi ∼= H2 for all i = 1, 2, . . . , n. Then the slim
subgraph of H is the line graph of a graph with n edges.
Example 6. Let H3 be the Hoffman graph consisting of two non-adjacent slim vertices and
one fat vertex, where both slim vertices are adjacent to the fat vertex. Let H be a connected
Hoffman graph which is the sum (1), where Hi ∼= H3 for all i = 1, 2, . . . , n. Then the slim
subgraph of H is the cocktail party graph on 2n vertices.
Example 7. Let H be a connected Hoffman graph which is the sum (1), where Hi ∼= H2 or
Hi ∼= H3 for all i = 1, 2, . . . , n. Then the slim subgraph of H is a generalized line graph.
Definition 8. For a Hoffman graph H , let A be its adjacency matrix,
A =
[
As C
CT O
]
in a labeling in which the fat vertices come last. Eigenvalues of H are the eigenvalues of the
real symmetric matrix As − CCT . Let λmin(H) denote the smallest eigenvalue of H . For
a connection of λmin(H) with the smallest eigenvalue of slim graphs, we refer [8, Proposi-
tion 5.3].
Hoffman claims that it is reasonable to believe that there is a sequence of numbers α1 =
−1 > α2 = −2 > α3 = −1 −
√
2 > α4 > · · · tending to some limit ᾱ, satisfying the
following condition: for each λ ∈ Λ1 with αi ≥ λ > αi+1, there is a positive integer f(λ)
such that, λmin(G) = λ and δ(G) ≥ f(λ) imply λ = αi. In order to deal with graphs
with λmin(G) < α2, in particular, those graphs G with α3 ≤ λmin(G) < α2, R. Woo and
A. Neumaier defined a new generalization of line graphs in [8], introducing the concept of a
Hoffman graph. The definition can be rewritten as follows using the notation introduced in
Definition 3.
Definition 9. Let H be a family of isomorphism classes of Hoffman graphs. An H -line
graph Γ is a subgraph of a graphH =
⊎n
i=1H
i such that [Hi] ∈H for all i ∈ {1, 2, . . . , n}.
In this case, we call H an H -cover graph of Γ. If Vs(Γ) = Vs(H), then we call H a strict
H -cover graph of Γ.
Two strict H -covers K and L of Γ are called equivalent, if there exists an isomorphism
ϕ : K → L such that ϕ|Γ is the identity automorphism of Γ.
R. Woo and A. Neumaier suggested α4 (≈ −2.4812) to be the smallest root of the
polynomial x3 + 2x2 − 2x− 2 in [8]. In their paper, some Hoffman graphs with the smallest
eigenvalue at least−1−
√
2 are given. They are listed in Figure 1 together with their smallest
eigenvalues λmin. Actually some of these graphs are not used in this paper, but we use the
same symbols as in [8] to avoid confusion.
84 Ars Mathematica Contemporanea 1 (2008) 81–98
H1, λmin = α1 H2, λmin = α2 H3, λmin = α2
H4, λmin = α2 H5, λmin = α3 H6, λmin = α3
H7, λmin = α3 H8, λmin = α3 H9, λmin = α3
Figure 1:
Theorem 10 (R. Woo and A. Neumaier [8]). Let α4 (≈ −2.4812) be the smallest root of
the polynomial x3 + 2x2 − 2x − 2. Then there exists an integer valued function f , defined
on the intersection of Λ1 with the half-open interval (α4, −1 −
√
2], such that if G is a
connected graph with α4 < λmin(G) ≤ −1 −
√
2, δ(G) ≥ f(λmin(G)), then G is an
{[H2], [H5], [H7], [H9]}-line graph.
In particular, λmin(G) = −1−
√
2.
In [8], R. Woo and A. Neumaier consider it one of the problems to find a complete list of
minimal forbidden subgraphs for slim (or arbitrary) {[H2], [H5], [H7], [H9]}-line graphs,
where H2, H5, H7 and H9 are graphs shown in Figure 1. If one finds such a list to be finite,
then it is expected that there exist finitely many maximal slim graphs, which have the smallest
eigenvalue at least −1−
√
2 and are not {[H2], [H5], [H7], [H9]}-line graphs, by applying
the star complement technique to the list (cf. [3]). This might lead to the determination of the
value f(−1−
√
2). But it seems very difficult to find all minimal forbidden subgraphs in this
case.
L. W. Beineke proved that line graphs are characterized by a collection of only nine
forbidden subgraphs (see [4]). Similarly, minimal forbidden subgraphs for the class of gen-
eralized line graphs were determined in [2]. In view of Theorem 10, it would be desirable
to determine minimal forbidden subgraphs for the class of slim {[H2], [H5], [H7], [H9]}-line
graphs. However, as the number of such minimal forbidden subgraphs seems very large, it
may make sense to consider first the smaller class of {[H2], [H5]}-line graphs.
A generalized cocktail party graph is a graph isomorphic to a clique with independent
edges removed. In [2], D. Cvetković, M. Doob and S. Simić showed the following theorem:
Theorem 11 (D. Cvetković, M. Doob and S. Simić). If G is a connected generalized line
graph with more than six vertices, then there exists a unique partition of the edges of G into
generalized cocktail party graphs satisfying the following conditions:
T. Taniguchi: On Graphs with the Smallest Eigenvalue at Least −1−
√
2, part I 85
(i) each vertex is in at most two generalized cocktail party graphs;
(ii) two generalized cocktail party graphs have at most one common vertex;
(iii) if two generalized cocktail party graphs have a common vertex, then it is adjacent to all
other vertices in both of them.
As this theorem was used to determine the minimal forbidden subgraphs for the class
of generalized line graphs, we intend to prove an analogous theorem for {[H2], [H5]}-line
graphs, then to determine the minimal forbidden subgraphs for the class of {[H2], [H5]}-line
graphs.
In this paper and the subsequent paper [9], we completely determine minimal forbidden
subgraphs for the class of slim {[H2], [H5]}-line graphs. First, in this paper, we show that
{[H2], [H5]}-line graphs are the same as the {[H2], [H3], [H5]}-line graphs. The latter family
turned out to be easier when dealing with cover graphs, and we prove the uniqueness of strict
{[H2], [H3], [H5]}-cover graphs. This result will then play a crucial role in obtaining an upper
bound on the number of vertices in a minimal forbidden subgraph. The details will be given
in the subsequent paper [9].
2 Some results on Hoffman graphs
For a Hoffman graph H , let E(H) denote the set of all edges of H . For a vertex v of a Hoff-
man graph H , we denote by NsH(v) (resp. N
f
H(v)) the set of all slim (resp. fat) neighbours
of v, and by NH(v) the set of all neighbours of v, i.e., NH(v) = NsH(v) ∪ N
f
H(v). We
write G ⊂ H if G is an induced subgraph of H . In particular, if Vs(G) = Vs(H), then we
write G ⊂∗ H . We denote by 〈S〉H the subgraph of H induced on a set of vertices S. If a
vertex x is adjacent to a vertex y, then we write x ∼ y. For a Hoffman graph H and a subset
S ⊂ Vs(H), let 〈〈S〉〉H denote the subgraph
〈〈S〉〉H = 〈S ∪ (
⋃
z∈S
NfH(z))〉H .
Also, define H − S, H − x by H − S = 〈〈Vs(H) \ S〉〉H , H − x = H − {x}, respectively,
where x ∈ Vs(H). Let ∅ be an empty set, and let φ be an empty graph. For graphs G
and H , we denote by G + H the disjoint union of G and H , and by nG the disjoint union
G + G + · · · + G of n copies of G. Let G ∗ H denote the graph consisting of the disjoint
union G+H , together with edges uv, for all u ∈ V (G) and all v ∈ V (H).
For the remainder of this section, we let H =
⊎n
i=0H
i be a graph for some family of
Hoffman subgraphsHi (i = 0, 1, . . . , n). If I ⊂ {0, 1, 2, . . . , n} andHI = 〈
⋃
i∈I V (H
i)〉H ,
then obviously HI =
⊎
i∈I H
i holds.
Lemma 12. Let S be a subset of Vs(H). Then
〈〈S〉〉H =
n⊎
i=0
(〈〈S ∩ Vs(Hi)〉〉H).
In particular, if x ∈ Vs(H0), then
H − x = (H0 − x) ] (
n⊎
i=1
Hi).
86 Ars Mathematica Contemporanea 1 (2008) 81–98
Proof. We verify the conditions (i)–(iv) of Definition 3. The conditions (i)–(iii) are obvious.
To verify the condition (iv), suppose x ∈ Vs(〈〈S ∩ Vs(Hi)〉〉H) = S ∩ Vs(Hi), y ∈ S ∩
Vs(Hj) and i 6= j. Then x and y have at most one common fat neighbour inH , and they have
one iff they are adjacent. Since the fat neighbours of x and y are all contained in 〈〈S〉〉H , x
and y have at most one common fat neighbour in 〈〈S〉〉H iff they are adjacent.
Lemma 13. If we construct a graph K containing H and its subgraph H̃0 containing H0,
by one of the following ways, then
K = H̃0 ] (
n⊎
i=1
Hi) (2)
holds:
(i) add a new slim vertex x and edges joining x to some of the vertices of Vs(H0); define
H̃0 to be the subgraph induced on V (H0) ∪ {x},
(ii) in addition to (i), add an edge joining x to a fixed fat vertex α of H0, and the edges
xy (y ∈ Vs(Hi), 1 ≤ i ≤ n, α ∼ y); define H̃0 to be the subgraph induced on
V (H0) ∪ {x},
(iii) add a new fat vertex β and edges joining β to some of the vertices of Vs(H0); define
H̃0 to be the subgraph induced on V (H0) ∪ {β},
Proof. In each of the cases (i)–(iii), we verify the conditions (i)–(iv) of Definition 3. The
conditions (i)–(ii) of Definition 3 are obvious for each of the cases (i)–(iii). The condition
(iii) of Definition 3 is obvious for the case (i). It is also easy to see for the cases (ii)–(iii), since
all the newly added edges joining slim and fat vertices are contained in H̃0. The condition (iv)
of Definition 3 is obvious for the case (i), since the new slim vertex x has no fat neighbour. It
is easy to see for the case (ii), since α is the unique fat neighbour of x. It is also easy for the
case (iii), since all the slim neighbours of β are in H̃0.
Lemma 14. Let K0 be a graph containing a subgraph G isomorphic to H0. Suppose that
for each x ∈ Vs(K0) \ Vs(G), |NK0(x) ∩ Vf (G)| ≤ 1. Then there exists a graph K with
K =
n⊎
i=0
Ki (3)
containing a subgraph isomorphic to H and Ki ∼= Hi for i = 1, 2, . . . , n.
Proof. We first prove the special case where Vf (K0) = Vf (G), by induction on |Vs(K0)| −
|Vs(G)|. The assertion is trivial when |Vs(K0)| − |Vs(G)| = 0, since we may take K = H .
Suppose |Vs(K0)|− |Vs(G)| > 0. Pick a vertex x ∈ Vs(K0)\Vs(G), and put L0 = K0−x.
Then L0 ⊃ G and, for each y ∈ Vs(L0)\Vs(G), |NL0(y)∩Vf (G)| = |NK0(y)∩Vf (G)| ≤ 1
by the assumption. Thus, by inductive hypothesis, there exists a graph L with L =
⊎n
i=0 L
i
containing a subgraph isomorphic to H , Li ∼= Hi (1 ≤ i ≤ n). We construct a graph K
from L by adding the vertex x as follows. First, we add edges joining x to vertices of L0
in such a way that the subgraph induced on L0 ∪ {x} is isomorphic to K0. If |NK0(x) ∩
Vf (G)| = 0, then NfK0(x) = ∅, so by Lemma 13(i), (3) holds. If |NK0(x) ∩ Vf (G)| = 1,
T. Taniguchi: On Graphs with the Smallest Eigenvalue at Least −1−
√
2, part I 87
then NfK0(x) = {α} for some fat vertex α. We then add the edges xy (y ∈ N
s
L(α)\Vs(L0)).
By Lemma 13(ii), (3) holds.
Next we consider the general case. Let L0 be the subgraph of K0 induced on Vs(K0) ∪
V (G). Then by the special case above, there exists a graph L with L =
⊎n
i=0 L
i containing
a subgraph isomorphic to H , and Li ∼= Hi (1 ≤ i ≤ n). It remains to construct a graph
K from L by adding the fat vertices V (K0) \ V (L0) = Vf (K0) \ Vf (L0) to L0. These fat
vertices can be added one by one, by Lemma 13(iii), in such a way that the resulting graph
is isomorphic to K0. Then (3) holds, and K has a subgraph isomorphic to L, and Ki ∼= Li
(1 ≤ i ≤ n). Thus K has a subgraph isomorphic to H , and Ki ∼= Hi (1 ≤ i ≤ n).
Lemma 15. Suppose that H is connected, H0 has a unique fat vertex α, and α is adjacent
to all the slim vertices of H0. Then 〈
⋃n
i=1 V (H
i)〉H is connected.
Proof. Let H ′ = 〈
⋃n
i=1 V (H
i)〉H . Since H is connected, α must have a slim neighbour
in H ′, and this implies α ∈ Vf (H ′). Then it suffices to show that every slim vertex x of
H ′ can be connected to α by a path in H ′. Since H is connected, then there exists a path
x = v0, v1, . . . , vr = α in H . If vi /∈ Vs(H0) for all i, then this path is entirely contained in
H ′. Otherwise, put
i = min{i | vi ∈ Vs(H0)} − 1.
Then v0, v1, . . . , vi ∈ V (H ′), vi ∈ {α} ∪ Vs(H ′), vi+1 ∈ Vs(H0). If vi = α, then x =
v0, v1, . . . , vi = α is a path in H ′. If vi ∈ Vs(H ′), then vi and vi+1 have a common fat
neighbour which must be α. Thus x = v0, v1, . . . , vi, α is a path in H ′.
3 A new generalization of line graphs
In this section, we let H be a family of isomorphism classes of graphs, except examples
where H is explicitly defined.
Lemma 16. Suppose H =
⊎n
i=0H
i, and assume that there exists an H -cover graph Ki of
Hi such that
|NKi(x) ∩ Vf (Hi)| ≤ 1 ∀x ∈ Vs(Ki) \ Vs(Hi) (4)
for each i. Then H is an H -line graph.
Proof. We prove the assertion by induction on k = |{i | [Hi] /∈H }|. The assertion is trivial
when k = 0, so assume k > 0. Then without loss of generality, we may assume [H0] /∈ H .
By the assumption, there exists an H -cover graph K0 =
⊎m
j=1 L
j of H0, [Lj ] ∈ H , such
that
|NK0(x) ∩ Vf (H0)| ≤ 1 ∀x ∈ Vs(K0) \ Vs(H0).
By Lemma 14, there exists a graph K̃ with K̃ =
⊎n
i=0 K̃
i containing a subgraph G isomor-
phic to H , K̃0 = K0, and K̃i ∼= Hi for i = 1, 2, . . . , n. Hence
K̃ = (
m⊎
j=1
Lj) ] (
n⊎
i=1
K̃i).
Now, by inductive hypothesis, we conclude that K̃ is an H -line graph, and so is its subgraph
G. Since H ∼= G, H is an H -line graph.
88 Ars Mathematica Contemporanea 1 (2008) 81–98
Lemma 17. Suppose that H satisfies the following condition:
[H] ∈H , H 6∼= H2 =⇒ |NfH(x)| ≤ 1 ∀x ∈ Vs(H). (5)
IfG is an H -line graph, then there exists an H -cover graphK ofG satisfying the condition
|NK(x) ∩ Vf (G)| ≤ 1 ∀x ∈ Vs(K) \ Vs(G). (6)
Proof. We may assume without loss of generality that G is connected. Since G is an H -line
graph, there exists an H -cover graph L of G, with L =
⊎m
j=1 L
j , [Lj ] ∈H . Put
J0 = {j | Lj ∼= H2 and Vs(Lj) 6⊂ Vs(G)},
J = {1, 2, . . . ,m} \ J0,
and let K be the subgraph of L induced on the set
⋃
j∈J V (L
j). Then we have
K =
⊎
j∈J
Lj . (7)
We claim V (G) ⊂ V (K). Indeed, if x ∈ Vs(G), then x ∈ Vs(Lj) for some j. If
Lj ∼= H2, then Vs(Lj) = {x} ⊂ Vs(G). This implies j ∈ J , and hence x ∈ Vs(K). If
α ∈ Vf (G), then, as G is connected and V (G) 6= {α}, α has a slim neighbour x ∈ Vs(G).
Then x ∈ Vs(Lj) for some j ∈ J by the previous case. This forces α ∈ Vf (Lj) by the
condition (iii) of Definition 3. Hence α ∈ Vf (K). Therefore, we have shown V (G) ⊂ V (K),
and K is an H -cover graph of G.
It remains to prove the assertion (6). Suppose x ∈ Vs(K) \ Vs(G). Then x ∈ Vs(Lj) for
some j ∈ J and, by (7), we have
|NK(x) ∩ Vf (G)| = |NLj (x) ∩ Vf (G)| ≤ |NfLj (x)|.
Since j ∈ J and x ∈ Vs(Lj) \ Vs(G), we must have Lj 6∼= H2. Since [Lj ] ∈ H , the
assumption (5) implies |NfLj (x)| ≤ 1. Therefore |NK(x) ∩ Vf (G)| ≤ 1.
Lemma 18. Suppose that H satisfies the condition (5). If H ′ is a family of isomorphism
classes of H -line graphs, then every H ′-line graph is an H -line graph.
Proof. Suppose H =
⊎n
i=0H
i, [Hi] ∈ H ′. We aim to show that H is an H -line graph.
Since Hi is an H -line graph for each i, Lemma 17 implies that there exists an H -cover
graph Ki of Hi satisfying the condition (4). By Lemma 16, we conclude that H is an H -
line graph.
Example 19. Let H = {[H2], [H3], [H5]}. Let H ′ = {[H2], [H5]}. Then H satisfies the
condition (5). Since H3 is a subgraph of H5, H3 is an H -line graph. By Lemma 18, every
H -line graph is an H ′-line graph. In particular, a slim generalized line graph is an H -line
graph.
Lemma 20. Suppose H =
⊎n
i=0H
i, and assume that there exists a strict H -cover graph
Ki of Hi for each i. Then H has a strict H -cover graph.
T. Taniguchi: On Graphs with the Smallest Eigenvalue at Least −1−
√
2, part I 89
Proof. We prove the assertion by induction on k = |{i | [Hi] /∈H }|. The assertion is trivial
when k = 0, so assume k > 0. Then without loss of generality, we may assume [H0] /∈ H .
By the assumption, there exists a strict H -cover graphK0 =
⊎m
j=1 L
j ofH0, [Lj ] ∈H . By
Lemma 14, there exists a graph K̃ with K̃ =
⊎n
i=0 K̃
i containing a subgraph G isomorphic
to H , K̃0 = K0, and K̃i ∼= Hi for i = 1, . . . , n. Then we obtain
K̃ = (
m⊎
j=1
Lj) ] (
n⊎
i=1
K̃i).
Now, by inductive hypothesis, we conclude that K̃ has a strict H -cover graph. Since
Vs(K̃) = Vs(G) and H ∼= G, H has a strict H -cover graph.
Lemma 21. Assume that, for any [G] ∈ H , and for any Hoffman subgraph K of G, there
exists a strict H -cover graph of K. Then every H -line graph has a strict H -cover graph.
Proof. Let Γ be an H -line graph. Let H =
⊎n
i=0H
i be an H -cover graph of Γ. Let
∆ = 〈〈Vs(Γ)〉〉H . then by Lemma 12,
∆ =
n⊎
i=0
〈〈Vs(Γ) ∩ Vs(Hi)〉〉H .
Since 〈〈Vs(Γ)∩Vs(Hi)〉〉H is a Hoffman subgraph ofHi and [Hi] ∈H , there exists a strict
H -cover graph Ki of 〈〈Vs(Γ) ∩ Vs(Hi)〉〉H . By Lemma 20, ∆ has a strict H -cover graph,
which is a strict H -cover graph of Γ, since Γ ⊂ ∆ and Vs(Γ) = Vs(∆).
Example 22. Let H = {[H2], [H3], [H5]}. Then H satisfies the condition (5). Moreover,
for any [G] ∈ H , and for any Hoffman subgraph K of G, there exists a strict H -cover
graph of K. Indeed, the only nontrivial case is the graph obtained from H5 by deleting the
unique slim vertex without slim neighbours. This graph has a strict H -cover graph which is
the join H2 ]H2 of two copies of H2 sharing a fat vertex. Therefore, by Lemma 21, every
H -line graph has a strict H -cover graph. In particular, every slim H -line graph has a strict
H -cover graph.
Lemma 23. Let H be a family of isomorphism classes of Hoffman graphs, satisfying the
condition (5). Let H be an H -line graph. Then,
(i) if u ∈ Vs(H), then |NfH(u)| ≤ 2,
(ii) if u, v are distinct slim vertices of H , then |NfH(u) ∩N
f
H(v)| ≤ 1.
Proof. Since H is an H -line graph, there exists an H -cover graph K =
⊎n
i=1K
i of H ,
[Ki] ∈H .
(i) Suppose |NfH(u)| ≥ 3. If u ∈ Vs(Ki), then N
f
H(u) ⊂ Vf (Ki) from Definition 3(iii).
Since |NfH(u)| ≥ 3, Ki 6∼= H2. Hence, by (5), |N
f
H(u)| ≤ 1. But this contradicts the
hypothesis.
(ii) Now NfH(u) ∩ N
f
H(v) ⊂ N
f
K(u) ∩ N
f
K(v) holds. If u, v ∈ Vs(Ki) for some i,
then by Definition 3(iii), we have NfK(u) ∩ N
f
K(v) ⊂ N
f
Ki(u) ∩ N
f
Ki(v). Thus the result
follows from the condition (5). If u ∈ Vs(Ki) and v ∈ Vs(Kj) for some distinct i, j, then
the |NfK(u) ∩N
f
K(v)| ≤ 1 by Definition 3(iv).
90 Ars Mathematica Contemporanea 1 (2008) 81–98
Lemma 24. Let H be a family of isomorphism classes of Hoffman graphs, satisfying the
condition (5). Let K and L be Hoffman graphs, satisfying the following conditions:
(i) K = K0 ]K ′, L = L0 ] L′,
(ii) 〈Vs(K)〉K and 〈Vs(K ′)〉K′ are connected,
(iii) [K0] = [L0] ∈H ,
(iv) K ′ =
⊎m1
i=1K
i, [Ki] ∈H ,
(v) L′ =
⊎m2
i=1 L
i, [Li] ∈H ,
(vi) ϕ : 〈Vs(K)〉K → 〈Vs(L)〉L: isomorphism,
(vii) ϕ′ : K ′ → L′: isomorphism,
(viii) ϕ|Vs(K′) = ϕ′|Vs(K′),
(ix) |Vf (K0)| = 1 if K0 6∼= H2,
(x) |Vs(K)| ≥ 6.
Then there exists an isomorphism ψ : K → L which is an extension of ϕ.
Proof. By (vii) and (viii)
ϕ(Vs(K ′)) = Vs(L′). (8)
Thus
ϕ(Vs(K0)) = ϕ(Vs(K) \ Vs(K ′)) = Vs(L) \ Vs(L′) = Vs(L0). (9)
By (ii), K is connected. Thus Vf (K0)∩Vf (K ′) 6= ∅. Also, (ii) and (vi) imply that 〈Vs(L)〉L
is connected. Thus L is connected. Hence Vf (L0)∩Vf (L′) 6= ∅. Observe that the conditions
are symmetric with respect to K and L.
Claim:
If u ∈ Vs(K ′) and v ∈ Vs(K0) are adjacent, thenNfL(ϕ(u))∩N
f
L(ϕ(v)) 6= ∅. If u ∈ Vs(L′)
and v ∈ Vs(L0) are adjacent, then NfK(ϕ−1(u)) ∩N
f
K(ϕ
−1(v)) 6= ∅.
Proof of Claim. Suppose u ∈ Vs(K ′) and v ∈ Vs(K0) are adjacent. Then
ϕ(u) ∈ ϕ(Vs(K ′)) = Vs(L′) and ϕ(v) ∈ Vs(L0),
by (8) and (9), respectively. Hence the claim follows from Definition 3(iv). Switching K,L
and replacing ϕ by ϕ−1 etc., we obtain the second statement.
T. Taniguchi: On Graphs with the Smallest Eigenvalue at Least −1−
√
2, part I 91
Case 1:
|Vf (K0) ∩ Vf (K ′)| ≥ 2 or |Vf (L0) ∩ Vf (L′)| ≥ 2.
Without loss of generality, we may suppose |Vf (K0) ∩ Vf (K ′)| ≥ 2. By (iii) and (ix),
K0 ∼= L0 ∼= H2. Let Vs(K0) = {x}, Vf (K0) = {f1, f2} ⊂ Vf (K ′). By (9), Vs(L0) =
{ϕ(x)}. Let Vf (L0) = {g1, g2}.
If {ϕ′(f1), ϕ′(f2)} = {g1, g2}, then the common extension of ϕ and ϕ′ is a desired
isomorphism ψ.
Next suppose |{ϕ′(f1), ϕ′(f2)}∩{g1, g2}| = 1. Then we may assume ϕ′(f1) /∈ {g1, g2}
and ϕ′(f2) = g2. Let u, u′ ∈ NsK′(f1) ⊂ Vs(K ′). By Lemma 23(i), |N
f
K′(u)| ≤ 2 and
|NfK′(u′)| ≤ 2. Hence |N
f
L′(ϕ(u))| ≤ 2 and |N
f
L′(ϕ(u
′))| ≤ 2. Since u and u′ are ad-
jacent to x in L′,
(
NfL′(ϕ(u)) ∪N
f
L′(ϕ(u
′))
)
\ {ϕ′(f1)} ⊂ {g1, g2}. By Lemma 23(ii),
NfL′(ϕ(u)) ∪N
f
L′(ϕ(u
′)) = {ϕ′(f1), g1, g2}. This implies f2 ∈ NfK′(u) ∪N
f
K′(u
′). Hence
|NfK′(u)∪N
f
K′(u
′)| ≥ |{f1, f2}| = 2. But this contadicts Lemma 23(ii). Thus |NsK′(f1)| =
1. Let {u1} = NsK′(f1). Since H is assumed to satisfy (5),K1 = 〈{u1, f1, ϕ′−1(g1)}〉K′ ∼=
H2 constitutes one of the family of subgraphs covering K ′. In particular, u1 is an iso-
lated vertex in 〈Vs(K ′)〉K′ . By (ii), we conclude Vs(K ′) = {u1}, and therefore K ′ =
K1. But then f2 ∈ Vf (K ′) is an isolated fat vertex. This is a contradiction. Hence
{ϕ′(f1), ϕ′(f2)} ∩ {g1, g2} = ∅.
Let u ∈ NsK(x). Then |N
f
K(u) ∩ {f1, f2}| = 1. Since ϕ(u) ∈ NsL(ϕ(x)), we also have
|NfL(ϕ(u)) ∩ {g1, g2}| = 1. This implies that there is a mapping
σ : NsK(x)→ {f1, f2} × {g1, g2}
defined by σ(u) = (σ1(u), σ2(u)), {σ1(u)} = NfK(u) ∩ N
f
K(x), {σ2(u)} = N
f
L(ϕ(u)) ∩
NfL(ϕ(x)). By Lemma 23, {ϕ′(σ1(u)), σ2(u)} = N
f
L(ϕ(u)). Hence σ is injective. Thus
|NsK(x)| ≤ 4. Moreover, every vertex u ∈ NsK(x) has two fat neighbours, so 〈{ϕ(u),
ϕ′(σ1(u)), σ2(u)}〉L′ ∼= H2 constitutes one of the family of subgraphs covering L′. Thus, if
u′ ∼ u for some u ∈ NsK(x), then ϕ(u′) ∈ NsL(ϕ′(f1)) ∪NsL(ϕ′(f2)) ∪NsL(g1) ∪NsL(g2).
Then ϕ(u′) ∈ NsL(ϕ(x)), hence u′ ∈ NsK(x). Therefore, Vs(K) = {x} ∪ NsK(x) has at
most 5 elements. But this contradicts the condition (x).
Case 2:
|Vf (K0) ∩ Vf (K ′)| = 1 and |Vf (L0) ∩ Vf (L′)| = 1.
First suppose K0 6∼= H2. By (iii) and (ix), |Vf (K0)| = |Vf (L0)| = 1, so let Vf (K0) =
{f}, Vf (L0) = {g}. If ϕ′(f) = g, then the common extension of ϕ and ϕ′ is a de-
sired isomorphism ψ. Hence we may suppose ϕ′(f) 6= g, i.e., ϕ′(f) /∈ Vf (L0). Suppose
|NsK′(f)| ≥ 2, and let u, u′ ∈ NsK′(f) be distinct. Let v ∈ NsK0(f). Since v ∼ f in K0,
u and u′ are adjacent to v in K. Hence, for each s ∈ {u, u′}, NfL(ϕ(s)) ∩ N
f
L(ϕ(v)) 6= ∅
by Claim, and therefore g ∈ NfL′(ϕ(s)) ∩ N
f
L0(ϕ(v)) ⊂ N
f
L′(ϕ(s)) since ϕ(v) ∈ V (L0),
ϕ(s) ∈ V (L′) and Vf (L0) ∩ Vf (L′) = {g}. Hence g ∈ NfL′(ϕ(u)) ∩ N
f
L′(ϕ(u
′)). Also,
ϕ′(f) ∈ NfK′(ϕ(u))∩N
f
K′(ϕ(u
′)). This contradicts Lemma 23. Hence |NsK′(f)| = 1, so let
NsK′(f) = {u}. Similarly, switching K,L and replacing ϕ by ϕ−1 etc., |NsL′(g)| = 1, hence
NsL′(g) = {ϕ(u)}. Since ϕ′−1(NsL′(g)) = NsK′(ϕ′−1(g)), NsK′(ϕ′−1(g)) = {u}. Hence
K ′ = 〈{u, f, ϕ′−1(g)}〉K′ ∼= H2. Let ρ be the automorphism of K ′ which switches the two
92 Ars Mathematica Contemporanea 1 (2008) 81–98
fat vertices f and ϕ′−1(g). Then ϕ′ ◦ ρ(f) = g. Replacing ϕ′ by ϕ′ ◦ ρ, the conditions (vii)
and (viii) are satisfied, so the proof reduces to the previously treated case where ϕ′(f) = g.
Next suppose K0 ∼= H2. Then L0 ∼= H2. Let f ′ ∈ Vf (K0) \ Vf (K ′), g′ ∈ Vf (L0) \
Vf (L′). The common extension ψ of ϕ and ϕ′ defined by ψ(f ′) = g′ is a desired isomor-
phism.
Remark 25. The hypothesis |Vs(K)| ≥ 6 in Lemma 24 is necessary. Indeed, let K = L =⊎4
i=0K
i be the graph defined as follows:
Ki = Li ∼= H2, Vs(Ki) = {ui} (0 ≤ i ≤ 4),
Vf (K0) = {f0, f1}, Vf (K1) = {f0, f2}, Vf (K2) = {f1, f2},
Vf (K3) = {f1, f3}, Vf (K4) = {f3, f0}.
Let K ′ = L′ =
⊎4
i=1K
i. Then 〈Vs(K ′)〉K′ ∼= C4 and 〈Vs(K)〉K ∼= K1 ∗ C4. Let ϕ be the
automorphism of 〈Vs(K)〉K which switches u2 and u4, leaving all the other vertices fixed.
Let ϕ′ be the automorphism of K ′ which switches (u2, u4), (f0, f2) and (f1, f3), leaving all
the other vertices fixed. Then all but the last hypotheses of Lemma 24 holds. If there exists
an automorphism ψ of K which is an extension of ϕ, then
ψ(f0) ∈ ψ(NfK(u0) ∩N
f
K(u1) ∩N
f
K(u4)) = N
f
K(u0) ∩N
f
K(u1) ∩N
f
K(u2) = ∅.
This is a contradiction.
4 The uniqueness of H -cover graphs
In this section, we let H = {[H2], [H3], [H5]}. By Example 22, every slim H -line graph
has a strict H -cover graph, and we shall show that a strict H -cover graph of a slim H -line
graph is unique up to equivalence, if the number of slim vertices is at least 8.
The following lemma is well known in the graph theory:
Lemma 26. Let Γ be a connected (slim) graph. Then there exists a (slim) vertex x in V (Γ)
such that Γ− x is connected.
Proof. See Problem 6(a) in section 6 of [7].
Lemma 27. If H =
⊎n
i=0H
i is a connected graph with [Hi] ∈ H and n > 0, then
Γ = 〈Vs(H)〉H is connected.
Proof. We prove the assertion by induction on n. The assertion is easy to verify when n = 1.
Suppose n > 1, and let H ′ = 〈
⋃n
i=1 V (H
i)〉H . Since H is connected, there exists α ∈
Vf (H0) ∩ Vf (H ′). Since [H0] ∈ H , every slim vertex of H0 is adjacent to α, and hence
every slim vertex of H0 has a slim neighbour in H ′. Since H ′ =
⊎n
i=1H
i is connected by
inductive hypothesis, we see that Γ is connected.
Example 28. The cocktail party graphCP (3) which is the unique 4-regular graph on 6 (slim)
vertices, has two non-isomorphic strict H -cover graphs (See Figure 2).
Example 29. All strict H -cover graphs of K1 ∗ 2(K1 +K2) are isomorphic, but not unique
up to equivalence (See Figure 3).
T. Taniguchi: On Graphs with the Smallest Eigenvalue at Least −1−
√
2, part I 93
⊃ CP(3) ⊂
Figure 2:
We verified by computer that the graph K1 ∗ 2(K1 + K2) is the only slim graph with 7
vertices whose strict H -cover graph is not unique up to equivalence. We also verified that
all slim graphs with 8 vertices have a unique strict H -cover graph up to equivalence.
Example 30. Let x be a slim vertex of a graph X with [X] ∈ H . Then there exists a graph
X̃ such that X − x ⊂∗ X̃ . Table 1 shows X̃ = X̃1 ] X̃2, for some graphs X̃1 and X̃2
satisfying [X̃1], [X̃2] ∈ H ∪ {[φ]}. In Table 1, the fat vertices of X̃ not in X are coloured
by white.
We shall now prove our main result.
Theorem 31. Let H = {H2, H3, H5}. Let Γ be a connected slim H -line graph with at least
8 vertices. Then there exists a strict H -cover graph of Γ, and it is unique up to equivalence.
Proof. From Example 22, every slim H -line graph has a strict H -cover graph. We prove
the uniqueness by induction on |V (Γ)|. Let K and L be strict H -cover graphs of Γ. As we
have mentioned above, the uniqueness of a strict H -cover graph of a connected slim H -line
graph has been verified by computer. Suppose |V (Γ)| ≥ 9.
Now, by Lemma 26, there exists a slim vertex x in V (Γ) such that Γ − x is connected.
Let K =
⊎m1
i=0K
i, [Ki] ∈ H , and L =
⊎m2
i=0 L
i, [Li] ∈ H , be strict H -cover graphs of
Γ. Without loss of generality, we may assume x ∈ Vs(K0)∩Vs(L0). We put K ′ =
⊎m1
i=1K
i
and L′ =
⊎m2
i=1 L
i. From Lemma 15, K ′ is connected. Hence, from Lemma 27, 〈Vs(K ′)〉K′
is connected. Therefore, we have shown that the hypothesis (ii) of Lemma 24 holds. Let
ϕ : 〈Vs(K)〉K → 〈Vs(L)〉L
be the identity automorphism of Γ = 〈Vs(K)〉K = 〈Vs(L)〉L. Since 9 ≤ |V (Γ)| ≤ 3(mj +
1), we have mj ≥ 2 (j = 1, 2). We construct a graph K̃0 from K0 according to Table 1.
Then either K̃0 = K0 − x or K̃0 is obtained from K0 − x by the operation described
in Lemma 13(iii). It then follows from Lemma 12 or Lemma 13 that we obtain a graph
K̃ = K̃0 ] K ′ which is a strict H -cover graph of K − x. Similarly, there exists a strict
H -cover graph L̃ = L̃0 ] L′ of L − x. Then by induction, the strict H -cover graphs K̃
and L̃ of Γ − x are equivalent. Hence, there exists an isomorphism ϕ̃: K̃ → L̃ such that
ϕ̃|Γ−x = 1Γ−x.
94 Ars Mathematica Contemporanea 1 (2008) 81–98
X
X − x φ
X̃ φ
X̃1 φ
X̃2 φ φ φ
Table 1:
T. Taniguchi: On Graphs with the Smallest Eigenvalue at Least −1−
√
2, part I 95
⊂∗ ∼=
Figure 3:
Claim 1:
If s ∈ Vs(K)\{x}, f ∈ Vf (K) are adjacent, then either sϕ̃(f) ∈ E(L0) or sϕ̃(f) ∈ E(L′).
If, in addition, s 6∼ x, then sϕ̃(f) ∈ E(L′) implies ϕ̃(f) /∈ V (L0).
Proof of Claim 1. Since ϕ̃ is an isomorphism which is the identity on Γ − x, s = ϕ̃(s) ∼
ϕ̃(f). Thus we have either sϕ̃(f) ∈ E(L0) or sϕ̃(f) ∈ E(L′) by Definition 3(iii). Suppose
s 6∼ x and sϕ̃(f) ∈ E(L′). Then NfL(s) ∩ N
f
L(x) = ∅ by Definition 3(iv). In particular,
ϕ̃(f) 6∼ x. Since [L0] ∈H , this implies ϕ̃(f) /∈ V (L0).
Claim 2:
If K0 ∼= H3 or H5, then Vs(K0) ⊂ Vs(L0).
Proof of Claim 2. Let Vf (K0) = {f}, and let y ∈ Vs(K0) \ {x} be such that x 6∼ y. Then
y ∼ f since [K0] ∈ H . By Claim 1, either yϕ̃(f) ∈ E(L0) or yϕ̃(f) ∈ E(L′) and
ϕ̃(f) /∈ V (L0).
Suppose yϕ̃(f) ∈ E(L0). If K0 ∼= H3, then Vs(K0) = {x, y} ⊂ Vs(L0). If K0 ∼= H5,
then let Vs(K0) = {x, y, z}. If z ∈ Vs(L′), then we have y ∼ z since ϕ̃(f) is a common
fat neighbour of y ∈ Vs(L0) and z = ϕ̃(z) ∈ Vs(L′), and also x ∼ z by the same reason.
96 Ars Mathematica Contemporanea 1 (2008) 81–98
Since K0 ∼= H5 has only one edge among its slim vertices, this is a contradiction. Therefore,
z ∈ Vs(L0), and Vs(K0) = {x, y, z} ⊂ Vs(L0).
Next suppose yϕ̃(f) ∈ E(L′) and ϕ̃(f) /∈ V (L0). We put K(1) = 〈〈NsK′(f)〉〉K′ . Since
K is connected, Vs(K(1)) 6= ∅. Let u ∈ Vs(K(1)). Then u ∼ x in K, i.e., in L. By Claim
1, either uϕ̃(f) ∈ E(L̃0) or uϕ̃(f) ∈ E(L′). Since ϕ̃(f) /∈ Vf (L0), ϕ̃(f) ∈ Vf (L′), and
therefore u ∈ Vs(L′). By Lemma 23(i), |NfK(1)(u)| ≤ 2, i.e., |N
f
K(1)
(u) \ {f}| ≤ 1. Since
u ∼ x in L, there exists g ∈ NfL′(u) ∩N
f
L0(x). Then obviously uϕ̃
−1(g) ∈ E(K ′). Hence
Nf
K(1)
(u) \ {f} = {ϕ̃−1(g)}. Thus ϕ̃(Nf
K(1)
(u) \ {f}) = {g} ⊂ Vf (L0), and
ϕ̃(Vf (K(1)) \ {f}) ⊂ Vf (L0). (10)
Let u′ ∈ Vs(K(1)) \ {u}. Then, similarly, there exists a unique fat vertex g′ ∈ NfL0(x) ∩
NfL′(u
′). Then ϕ̃−1(g′) ∈ NfK′(u′). Since u and u′ have a unique common fat neighbour f
from Lemma 23(ii), ϕ̃−1(g) 6= ϕ̃−1(g′), i.e., g 6= g′. This implies
|Vs(K(1))| = |NfL0(x) ∩ ϕ̃(Vf (K
(1)))|. (11)
Hence, since |Vf (L0)| ≤ 2, |Vs(K(1))| ≤ 2. Thus
|Vs(K)| − |Vs(K0)| − |Vs(K(1))| ≥ 9− 3− 2 > 0. (12)
We put
K(2) = 〈〈(
⋃
α∈Vf (K(1))
α6=f
NsK′(α)) \ Vs(K(1))〉〉K′ .
By (12), Vs(K(2)) 6= ∅. Let v ∈ Vs(K(2)). From Lemma 23(ii), |NfK′(u)∩N
f
K′(v)| ≤ 1 for
any u ∈ Vs(K(1)). Hence v 6∼ f in K, i.e., v 6∼ x in Γ. Moreover ϕ̃(NfK′(v)∩ Vf (K(1))) ⊂
ϕ̃(Vf (K(1)) \ {f}) ⊂ Vf (L0) by (10). Hence, by Claim 1, v ∈ Vs(L0), i.e.,
Vs(K(2)) ⊂ Vs(L̃0). (13)
This implies L0 ∼= H3 or H5. Hence, by (13),
|Vs(K(2))| ≤ |Vs(L0) \ {x}| ≤ 2. (14)
Moreover, by (13) and Definition 3(iii), ϕ̃(E(K(2))) ⊂ E(L̃0), i.e.,
ϕ̃(K(2)) ⊂ L̃0. (15)
Let Vf (L0) = {g}. By (10), ϕ̃(Vf (K(1)) \ {f}) = {g}. Hence Vf (K(1)) = {f, ϕ̃−1(g)}.
Moreover, by (11),
|Vs(K(1))| = |{g} ∩ ϕ̃({f, ϕ̃−1(g)})| = |{g}| = 1. (16)
Moreover,
Vs(L̃0) = NsL̃0(g) = ϕ̃
−1(Ns
L̃0
(g)) ⊂ Ns
K̃
(ϕ̃−1(g)).
T. Taniguchi: On Graphs with the Smallest Eigenvalue at Least −1−
√
2, part I 97
Since u /∈ Vs(L0), Vs(L̃0) ⊂ NsK̃(ϕ̃
−1(g)) \ {u}. Hence, since Ns
K̃
(ϕ̃−1(g)) = Vs(K(1))∪
Vs(K(2)) = {u} ∪ Vs(K(2)), Vs(L̃0) ⊂ Vs(K(2)). Thus, by (15),⋃
α∈Vf (K(2))
α6=ϕ̃−1(g)
Ns
K̃
(α) =
⋃
β∈ϕ̃(Vf (K(2)))
β 6=g
Ns
ϕ̃(K̃)
(β) ⊂
⋃
β∈Vf (L̃0)
β 6=g
Ns
L̃
(β) = Vs(L̃0) ⊂ Vs(K(2)).
Hence, sinceK ′ is connected, K ′ = K(1)]K(2). Thus |Vs(K̃)| = |Vs(K̃0)|+ |Vs(K(1))|+
|Vs(K(2))|. Hence, by (15) and (16), |V (Γ)| ≤ 6 since |Vs(K̃0)| ≤ 2. But this contradicts
the hypothesis.
Claim 3:
Vs(K0) = Vs(L0).
Proof of Claim 3. Suppose K0 6∼= H2. By Claim 2, Vs(K0) ⊂ Vs(L0). Since |Vs(K0)| ≥
2 > |Vs(H2)|, we have L0 6∼= H2, and hence the same argument yields Vs(L0) ⊂ Vs(K0).
Therefore, Vs(K0) = Vs(L0). Similarly, L0 6∼= H2 implies Vs(K0) = Vs(L0). If K0 ∼=
L0 ∼= H2, then Vs(K0) = {x} = Vs(L0).
Obviously the hypotheses (i), (iv), (v), (vi), (ix) and (x) of Lemma 24 hold. The hypoth-
esis (ii) holds as mentioned above. Moreover, since [K0], [L0] ∈ H , by Claim 3, it follows
that K0 ∼= L0, i.e., the hypothesis (iii) of Lemma 24 holds.
Since Vs(K̃0) ⊂ V (Γ − x), we have ϕ̃(Vs(K̃0)) = 1Γ−x(Vs(K̃0)) = Vs(K̃0) =
Vs(K0)\{x} = Vs(L0)\{x} = Vs(L̃0). Now ϕ̃(K̃)−Vs(L̃0) = ϕ̃(K̃0]K ′)−ϕ̃(Vs(K̃0)) =
ϕ̃(K̃0]K ′−Vs(K̃0)) = ϕ̃(K ′), and L̃−Vs(L̃0) = L̃0]L′−Vs(L̃0) = L′. Since ϕ̃(K̃) = L̃,
we obtain ϕ̃(K ′) = L′. Moreover, since ϕ̃|Γ−x = 1Γ−x and Vs(K ′) ⊂ Vs(Γ − x),
ϕ̃|Vs(K′) = 1Vs(K′) = ϕ|Vs(K′). Therefore the isomorphism ϕ̃|K′ : K ′ → L′ satisfies
ϕ|Vs(K′) = ϕ̃|Vs(K′). By putting ϕ′ = ϕ̃|K′ , we obtain the hypotheses (vii) and (viii) of
Lemma 24.
Hence the hypotheses (i)–(x) of Lemma 24 hold, and therefore there exists an isomor-
phism ψ: K → L which is an extension of the identity mapping ϕ.
Acknowledgements The author would like to thank his advisor, Professor Akihiro Mune-
masa, for his valuable suggestions and fruitful discussions on the topic. The author is also
grateful to Professors Dragoš Cvetković and Arnold Neumaier for their valuable comments
on the presentation of the results contained in this paper.
References
[1] P. J. Cameron, J. M. Goethals, J. J. Seidel, and E. E. Shult, Line graphs, root systems and elliptic
geometry, J. Algebra 43 (1976), 305–327.
[2] D. Cvetković, M. Doob and S. Simić, Generalized line graphs, J. Graph Theory 5 (1981), 385–
399.
[3] D. Cvetković, M. Lepović, P. Rowlinson and S. K. Simić, The maximal exceptional graphs,
J. Combin. Theory Ser. B 86 (2002), no. 2, 347–363.
[4] D. Cvetković, P. Rowlinson, S. K. Simić, Spectral Generalizations of Line Graphs — On Graphs
with Least Eigenvalue −2, Cambridge Univ Press, 2004.
98 Ars Mathematica Contemporanea 1 (2008) 81–98
[5] D. Cvetković, P. Rowlinson, S. K. Simić, Constructions of the maximal exceptional graphs with
largest degree 28, Department of Computing Science and Mathematics, University of Stirling,
Scotland, Technical Report CSM-156, Stirling, 2000.
[6] A. J. Hoffman, On graphs whose least eigenvalue exceeds −1 −
√
2, Linear Algebra Appl. 16
(1977), 153–165.
[7] L. Lovász, Combinatorial Problems and Exercises, 2nd edition, North-Holland, 1993.
[8] R. Woo and A. Neumaier, On graphs whose smallest eigenvalue is at least −1 −
√
2, Linear
Algebra Appl. 226/228 (1995), 577–591.
[9] T. Taniguchi, On graphs with the smallest eigenvalue at least −1−
√
2, part II, in preparation.
[10] The Magma Computational Algebra System for Algebra, Number Theory and Geometry. URL:
http://magma.maths.usyd.edu.au/magma/