Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 243–258
On graphs with the smallest eigenvalue at least
−1−
√
2, part II
Tetsuji Taniguchi
Matsue College of Technology
Nishiikuma-cho 14-4, Matsue, Shimane 690-8518, Japan
Received 25 December 2010, accepted 30 December 2011, published online 22 March 2012
Abstract
This is a continuation of the article with the same title. In this paper, the family H is
the same as in the previous paper [11]. The main result is that a minimal graph which is
not an H -line graph, is just isomorphic to one of the 38 graphs found by computer.
Keywords: Generalized line graph, spectrum.
Math. Subj. Class.: 05C50
1 Introduction
In the previous paper [11], we proved the uniqueness of strict {[H2], [H3], [H5]}-cover
graphs. This result plays a crucial role in obtaining an upper bound on the number of
vertices in a minimal forbidden subgraph.
In this paper, we completely determine minimal forbidden subgraphs for the class of
slim {[H2], [H3], [H5]}-line graphs. By computer, we obtain such graphs (cf. Figure 2).
The smallest eigenvalue of the minimal forbidden subgraph G5,2 is less than−1−
√
2, and
others are greater than or equal to −1 −
√
2. We know that the smallest eigenvalues of
{[H2], [H3], [H5]}-line graphs are greater than or equal to −1 −
√
2 (cf. Theorem 3.7 of
[12]). These mean that, if a graph does not contain subgraphs in Figure 2, then it is a slim
{[H2], [H3], [H5]}-line graph, and has the smallest eigenvalue at least −1−
√
2.
We use the same notation as in [11].
Definition 1.1. A Hoffman graph is a graph H with vertex labeling V (H) → {s, f},
satisfying the following conditions:
(i) every vertex with label f is adjacent to at least one vertex with label s;
E-mail address: tetsuzit@matsue-ct.ac.jp (Tetsuji Taniguchi)
Copyright c© 2012 DMFA Slovenije
244 Ars Math. Contemp. 5 (2012) 243–258
(ii) 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 graph H induced on Vs(H) is called the slim subgraph of H .
We draw Hoffman graphs by depicting vertices as large (small) black dots if they are fat
(slim).
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:
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. For a vertex v of a Hoffman 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) = N
s
H(v) ∪ N
f
H(v). We write G ⊂ H if G is an induced subgraph of H . We
denote by 〈S〉H the subgraph of H induced on a set of vertices S. 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 ∈ V (H). Let ∅ be an empty set, and let φ be an empty graph.
Definition 1.2. Let H be a Hoffman graph, and let Hi (i = 1, 2, . . . , n) be a family of
subgraphs of H . The graph H is said to be the sum of Hi (i = 1, 2, . . . , n), denoted
H =
n⊎
i=1
Hi, (1.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);
T. Taniguchi: On graphs with the smallest eigenvalue at least −1−
√
2, part II 245
(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.
Definition 1.3. Let H be a family of isomorphism classes of Hoffman graphs. An H -
line graph Γ is a subgraph of a graph H =
⊎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 equiva-
lent, if there exists an isomorphism ϕ : K → L such that ϕ|Γ is the identity automorphism
of Γ.
For the remainder of this section, we assume H = {[H2], [H3], [H5]} (cf. Figure 1).
In our previous paper [11], we proved the following theorem:
Theorem 1.4. Let Γ be a connected slim H -line graph with at least 8 vertices. Then a
strict H -cover graph of Γ is unique up to equivalence.
Every subgraph of an H -line graph is an H -line graph. Thus, it is desirable to deter-
mine all minimal slim non H -line graphs. If Γ is a minimal slim non H -line graph with
at least 9 vertices, then we can use Theorem 1.4 to derive a contradiction (refer to Section
4 for the details of the proof). Enumerating all the slim non H -line graphs with at most
8 vertices by comupter, we obtain the following theorem which is the main result in this
paper:
Theorem 1.5. If Γ is a minimal slim non H -line graph, then Γ is isomorphic to one of the
graphs in Figure 2.
2 Forbidden graphs found by computer search
In this section, we assume H = {[H2], [H3], [H5]} (cf. Figure 1). Proposition 2.1 is
the main result in this section. It is very hard to obtain the propositions without computer
search. In this paper, we have computed by the software MAGMA [9]. In order to prove
the propositions, we show some lemmas.
Let Xn be the family of isomorphism classes of connected slim graphs with n vertices.
Brendan McKay gives collections of simple graphs on his web site (cf. [10]). From the
data on this web site, we can generate Xn. Let Sn be the family of isomorphism classes of
connected slim H -line graphs with n vertices. By computer, we obtain
Xn = Sn (n = 1, 2, 3, 4) and X5 \ S5 = {[G5,1], [G5,2]} (cf. Figure 2). (2.1)
We define Fn to be the family of isomorphism classes of minimal slim non H -line graphs
with n vertices. From (2.1), Fi = ∅ (i = 1, 2, 3, 4) and F5 = {[G5,1], [G5,2]}. Removing
those graphs which contain G5,1 or G5,2 from X6 \ S6, we obtain F6 = {[G6,i]| i =
1, 2, . . . , 28}. Similarly we obtain F7 = {[G7,i]| i = 1, 2, . . . , 7}, F8 = {[G8,1]}, and
F9 = ∅ (cf. Figure 2). Hence the following proposition holds:
Proposition 2.1. Let Γ be a minimal slim non H -line graph. If |V (Γ)| ≤ 9, then [Γ] ∈
F5 ∪F6 ∪F7 ∪F8.
Actually, the conclusion of the proposition holds without the assumption |V (Γ)| ≤ 9.
246 Ars Math. Contemp. 5 (2012) 243–258
G5,1 G5,2 G6,1 G6,2 G6,3
G6,4 G6,5 G6,6 G6,7 G6,8
G6,9 G6,10 G6,11 G6,12 G6,13
G6,14 G6,15 G6,16 G6,17 G6,18
G6,19 G6,20 G6,21 G6,22 G6,23
G6,24 G6,25 G6,26 G6,27 G6,28
G7,1 G7,2 G7,3 G7,4 G7,5
G7,6 G7,7 G8,1
Figure 2:
T. Taniguchi: On graphs with the smallest eigenvalue at least −1−
√
2, part II 247
3 Some useful lemmas
A vertex of a graph is called a pendant vertex if it has degree 1.
Lemma 3.1. Let H = H0 ]H1 be a connected graph. Suppose that Vf (H0)∩Vf (H1) =
{α} and NsH0(α) = Vs(H0). Then H1 is connected.
Proof. Put F = Vf (H0) \ {α} and K = H0 − F . Then F ∩ Vf (H1) = ∅. Hence
H − F = K ]H1 and H − F is connected. Since α is a unique fat vertex of K which is
adjacent to all the slim vertices of K, Lemma 15 of [11] implies that H1 is connected.
Lemma 3.2. Let H be a family of isomorphism classes of Hoffman graphs, satisfying the
following condition:
[H] ∈H , H 6∼= H2 =⇒ |NfH(x)| ≤ 1 ∀x ∈ Vs(H).
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. See Lemma 23 of [11].
From [8, §6, Problem 6(c)], we obtain the following lemma:
Lemma 3.3. Let Γ be a connected slim graph. If Γ is neither a complete graph nor a cycle,
then there exists a non-adjacent pair {x, y} in V (Γ) such that Γ− {x, y} is connected.
For the remainder of this section, we assume H = {[H2], [H3], [H5]} (cf. Figure 1).
Lemma 3.4. Let H =
⊎n
i=0H
i be a Hoffman graph satisfying [Hj ] ∈ H for j =
0, 1, . . . , n. Let V be a subset of Vs(H), and let K = 〈〈V 〉〉H . Then there exist subgraphs
Ki (i = 0, 1, . . . , n′) of K such that
K =
n′⊎
i=0
Ki, [Kj ] ∈H ∪ {[H1]} for j = 0, 1, . . . , n′.
Proof. Put Li = 〈〈V ∩ Vs(Hi)〉〉Hi . Obviously [Li] ∈ H ∪ {[φ], [H1], [H ′]}, where H ′
is the sum H1 ]H1 of two copies of H1 sharing a fat vertex. Since K =
⊎n
i=0 L
i by [11,
Lemma 12], the lemma holds.
Lemma 3.5. Let Γ be a connected slim H -line graph. Then there exists a connected strict
H -cover graph H =
⊎n
i=0H
i of Γ. Conversely, if H =
⊎n
i=0H
i is a connected graph
with [Hi] ∈H and n > 0, then Γ = 〈Vs(H)〉H is connected.
Proof. The first part follows from Example 22 of [11]. We prove the second part by in-
duction 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, Vf (H0) ∩ Vf (H ′) 6= ∅. Pick α ∈
Vf (H
0) ∩ Vf (H ′). Then 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.
248 Ars Math. Contemp. 5 (2012) 243–258
Lemma 3.6. If
⊎m1
i=0K
i =
⊎m2
i=0 L
i and [Ki], [Li] ∈H for each i, then m1 = m2, and
{Ki | 0 ≤ i ≤ m1} = {Li | 0 ≤ i ≤ m2}.
Proof. It suffices to prove Ki = Lj whenever Vs(Ki) ∩ Vs(Lj) 6= ∅. We may suppose
without loss of generality that i = j = 0. IfK0 ∼= H2, thenK0 has a unique slim vertex, so
Vs(K
0) ⊂ Vs(L0). By Definition 1.2(iii), we have K0 ⊂ L0. This implies |Vf (L0)| ≥ 2,
hence L0 ∼= H2, and therefore K0 = L0. The same conclusion holds when L0 ∼= H2, so
we suppose [K0], [L0] ∈ {[H3], [H5]} for the rest of the proof. If s1 ∈ Vs(K0) ∩ Vs(L0),
then there exists s2 ∈ Vs(K0) not adjacent to s1. Since s1 and s2 have a common fat
neighbour in K0, Definition 1.2(iv) forces s2 ∈ Vs(L0). This implies Vs(K0) ⊂ Vs(L0)
if K0 ∼= H3. If K0 ∼= H5, then consider the third slim vertex s3 of K0. We may assume
without loss of generality that s3 is not adjacent to s1. Since s1 and s3 have a common
fat neighbour in K0, Definition 1.2(iv) forces s3 ∈ Vs(L0). Thus Vs(K0) ⊂ Vs(L0).
Switching the roles of K0 and L0, we obtain Vs(L0) ⊂ Vs(K0). Therefore we conclude
Vs(K
0) = Vs(L
0), and hence K0 = L0.
Lemma 3.7. Suppose H = H0 ]H1, S ⊂ Vs(H1), and H2 = 〈〈S〉〉H1 . Then 〈V (H0) ∪
V (H2)〉H = H0 ]H2.
Proof. Routine verification.
(i) (ii) (iii) (iv)
H0
H0 − x φ
H̃0 φ
Table 1:
Lemma 3.8. Let H = H0 ] H1 be a connected Hoffman graph satisfying [H0] ∈ H .
Let x be a slim vertex of H0. Then there exists a strict H -cover graph H̃ = H̃0 ]H1 of
H − x, and one of the following holds:
(i) H̃0 = φ,
T. Taniguchi: On graphs with the smallest eigenvalue at least −1−
√
2, part II 249
(ii) H̃0 ∼= H2, and one of the fat vertices of H̃0 is a pendant vertex in H ,
(iii) H̃0 = K1 ]K2, K1 ∼= K2 ∼= H2, K1 and K2 have a fat vertex in common, and the
other fat vertices of H̃0 are pendant vertices in H ,
(iv) H̃0 ∼= H3.
Proof. This is shown in the proof of Theorem 31 in [11], using Table 1, Lemma 12 and
Lemma 13 in [11].
For a Hoffman graph H =
⊎n
i=0H
i and a subset J of {0, 1, . . . , n}, we write H(J) =⊎
i∈J H
i.
Lemma 3.9. Let H =
⊎n
i=0H
i be a connected Hoffman graph satisfying Hj ∼= H2, H3
or H5 for j = 0, 1, . . . , n. Let V be a subset of Vs(H) such that 〈〈V 〉〉H is connected. Let
I = {i | Hi ∼= H2, 0 ≤ i ≤ n}, and let I ′ = {i ∈ I | Vs(Hi) ⊂ V }. Then,
(i) if I ′ 6= ∅, then H(I ′) is connected, and in particular, H(I) is connected,
(ii) if I 6= ∅, then Vf (H(I)) = Vf (H).
Proof. Put J = {i | 0 ≤ i ≤ n, Vs(Hi) ∩ V 6= ∅} so that I ′ = I ∩ J . Since 〈〈V 〉〉H is
connected, so is H(J). Since the removal of Vs(Hi) with i ∈ J \ I ′ preserves connectivity
by Lemma 3.1, we conclude that H(I ′) is connected.
Suppose Vf (H(I)) 6= Vf (H). Then there exists a fat vertex f ∈ Vf (H) \ Vf (H(I)).
Since 〈〈NsH(f)〉〉H has the unique fat vertex f , it is a connected component of H . But this
contradicts the assumption that H is connected and I 6= ∅. Hence Vf (H(I)) = Vf (H).
4 Main theorem: The minimal forbidden subgraphs
In this section, we assume H = {[H2], [H3], [H5]} (cf. Figure 1). Let F1, F2, . . . , F9 be
the Hoffman graphs depicted in Figure 3.
F1 F2 F3 F4 F5
F6 F7 F8 F9
Figure 3:
Let G = F ]K be a connected Hoffman graph such that Vf (F ) ⊂ Vf (K) and
K =
n⊎
i=0
Hi, [Hj ] ∈H ∪ {[H1]} for j = 0, 1, . . . , n. (4.1)
250 Ars Math. Contemp. 5 (2012) 243–258
When F ∼= F1, F3, F4, F6, F7 or F9, Table 2 gives a list of slim subgraphs G′ guaranteed
to exist in G, under some additional assumptions. The assumptions are given in terms
of c(K) and |Vs(K)|, where c(K) denotes the number of connected components of K.
For example, if F ∼= F1, c(K) = 2, and |Vs(K)| = 4, then G has a slim subgraph G′
isomorphic to G5,1, G5,2, G6,3, or G6,21, while if F ∼= F3 and c(K) = 2, then Table 2
gives no conclusion. The results in Table 2 were obtained by computer.
F c(K) |Vs(K)| G′
(a)
F1
1 5 G5,1 G5,2 G6,3 G6,6 G6,12 G6,14 G6,21 G7,5
(b) 2 4 G5,1 G5,2 G6,3 G6,21
(c) F3
1
5
G5,1 G6,5 G6,7 G6,9 G6,11 G6,12 G6,13 G7,6
G6,19 G6,17 G6,23 G6,24 G6,25 G6,27
(d) F4 4 G5,1 G6,5 G6,8 G6,15 G6,18
(e) F6 G5,2 G6,14 G6,19 G6,22 G6,26 G6,28 G7,3
(f) F7 2 G6,1 G6,6 G6,16
(g) F9 4 G6,2 G6,3 G7,1 G7,2
Table 2:
Lemma 4.1. Let G = F ]H be a Hoffman graph satisfying
H =
n⊎
i=0
Hi, (4.2)
Vf (F ) ⊂ Vf (H), (4.3)
Hj ∼= H2 for j = 0, 1, . . . , n, (4.4)
H is connected. (4.5)
Suppose F ∼= Fi for some i ∈ {2, 3, 5, 8}, and let F ′ be a subgraph of F such that
F ′ ∼= F3. Let Vf (F ′) = {f0, f1}. If there is no edge between NsH(f0) and NsH(f1), then
G has a slim subgraph isomorphic to G5,1, G6,17 or G6,27.
Proof. First we note NsH(f0) ∩ NsH(f1) = ∅ by Definition 1.2(iv). In particular, we have
n > 0. From Lemma 3.5, there exists a path in 〈Vs(H)〉H connecting a vertex in NsH(f0)
and a vertex in NsH(f1). Let P be such a path with shortest length. The length of P is at
least 2 by the assumption. SinceG contains F ′]H as a subgraph by Lemma 3.7, it suffices
to show that F ′ ]H contains a desired slim subgraph. If P has length 2 or 3, then F ′ ]H
has a subgraph isomorphic to G5,1 or G6,17, respectively. If the length of P is at least 4,
then F ′ ]H has a subgraph isomorphic to G6,27.
Lemma 4.2. Let G = F ]H be a Hoffman graph satisfying (4.2)–(4.5). Suppose F ∼= F4,
Vf (F ) = {f0, f1, f2} with |NsF (f0)| = 2. If 〈NsH(f0) ∪ NsH(f1) ∪ NsH(f2)〉H is not
connected, then G has a slim subgraph isomorphic to G5,1, G6,17, G6,23 or G6,27.
Proof. By (4.3), |Vf (H)| ≥ |Vf (F )| = 3, and therefore n > 0. From Lemma 3.5, there
exists a path in 〈Vs(H)〉H connecting a vertex inNsH(f0) and a vertex inNsH(f1)∪NsH(f2)
such that the two vertices are not adjacent in H , by the assumption. Let P = u ∼ v ∼
· · · ∼ w be such a path with shortest length, where u ∈ NsH(f1) ∪ NsH(f2) and w ∈
T. Taniguchi: On graphs with the smallest eigenvalue at least −1−
√
2, part II 251
NsH(f0). Then v /∈ NsH(f1) ∪ NsH(f2), and we may assume u ∈ NsH(f1) without loss
of generality. Then V (P ) ∩ NsH(f1) = {u}. If u ∼ f2, then N
f
H(u) = {f1, f2}, which
implies NfH(u) ∩N
f
H(v) = ∅, contradicting u ∼ v. Thus u /∈ NsH(f2).
Put S = V (P )∩NsH(f2). Suppose S = ∅. By Lemma 3.7, F ]〈〈V (P )〉〉H ⊂ G, while
f2 has no slim neighbour in 〈〈V (P )〉〉H . This implies (F − f2) ] 〈〈V (P )〉〉H ⊂ G. Since
F −f2 ∼= F3, the lemma follows from Lemma 4.1. Suppose S 6= ∅. Since P is the shortest
path, w is adjacent to exactly one vertex s1 in S, and |S| = 2. Put S \ {s1} = {s2}, and let
w′ be the neighbour of s2 different from s1 in P . Then 〈Vs(F ) ∪ S ∪ {w,w′}〉G ∼= G6,23,
and hence G contains a subgraph isomorphic to G6,23.
Lemma 4.3. Let G = F ]H be a Hoffman graph satisfying (4.2), (4.3) and the following
conditions:
F is connected, (4.6)
[Hj ] ∈H for j = 0, 1, . . . , n. (4.7)
Let V is a subset of Vs(H), and let K = 〈〈V 〉〉H . If Vf (F ) ⊂ Vf (K), and every vertex of
V can be joined by a path in K to a fat vertex of F , then G contains a connected subgraph
F ]K satisfying (4.1).
Proof. From Lemma 12 of [11], 〈〈Vs(F ) ∪ V 〉〉G = F ] K. Since F is connected and
every vertex of V can be joined by a path in K to a fat vertex of F , F ]K is connected.
From Lemma 3.4, K satisfies (4.1).
Lemma 4.4. LetG = F ]H be a Hoffman graph satisfying (4.2), (4.3), (4.7), and F ∼= Fi
for some i ∈ {1, 2, . . . , 9}. Let
m(F ) =

2 if F ∼= F7,
4 if F ∼= F4, F6 or F9,
5 otherwise.
If H is connected and |Vs(H)| ≥ m(F ), then G has a slim subgraph isomorphic to one of
the graphs in Figure 2.
Proof. Let I = {i | Hi ∼= H2, 0 ≤ i ≤ n}. First we suppose I = ∅. Then, since
Hi ∼= H3 or H5, |Vf (Hi)| = 1 for all i ∈ {0, 1, . . . , n}. This implies |Vf (H)| = 1
since H is connected. Hence F ∼= F6, F7 or F9 by (4.3). Suppose F ∼= F7. Since H3 is
a subgraph of H5, there exists a subgraph K of H such that K ∼= H3. Then G contains
F]K as a subgraph from Lemma 3.7. Since F]K satisfies the assumptions of Table 2, the
conclusion holds. Suppose F ∼= F6 or F9. Since |Vs(H)| ≥ 4 and H3 is a subgraph of H5,
there exists a subgraph K of H isomorphic to the sum H3 ]H3 sharing a fat vertex. Then
G contains F ]K as a subgraph from Lemma 3.7. Since F ]K satisfies the assumptions
of Table 2, the conclusion holds. In the remaining part of this proof, we suppose I 6= ∅.
For a subset J of {0, 1, . . . , n}, we write H(J) =
⊎
i∈J H
i.
Claim 4.5. The graph 〈Vs(H)〉H is connected.
Since |Vs(H)| ≥ m(F ) ≥ 2 and I 6= ∅, n > 0. Hence, from the last part of Lemma 3.5,
〈Vs(H)〉H is connected.
252 Ars Math. Contemp. 5 (2012) 243–258
Claim 4.6. Vf (F ) ⊂ Vf (H(I)).
From Lemma 3.9(ii), Vf (H(I)) = Vf (H). By (4.3), Vf (F ) ⊂ Vf (H(I)).
Claim 4.7. Suppose F ∼= F1, F3, F4, F6, F7 or F9, and that there exists I ′ ⊂ I such that
|I ′| ≤ m(F ), Vf (F ) ⊂ Vf (H(I ′)) and H(I ′) is connected. Then the lemma holds.
If |I ′| = 1, then obviously 〈Vs(H(I ′))〉H is connected. If |I ′| > 1, then, from the last
part of Lemma 3.5, 〈Vs(H(I ′))〉H is connected. The graph 〈Vs(H)〉H is also connected
from Claim 4.5. Since |Vs(H(I ′))| = |I ′| ≤ m(F ) ≤ |Vs(H)|, there exists a subset V such
that Vs(H(I ′)) ⊂ V ⊂ Vs(H), |V | = m(F ) and 〈V 〉H is connected. Put K = 〈〈V 〉〉H .
ThenK is connected and Vf (F ) ⊂ Vf (K). HenceG contains a connected subgraph F ]K
satisfying (4.1) by Lemma 4.3. Therefore the assumptions of Table 2 are satisfied. Hence
the lemma holds.
Claim 4.8. If F ∼= F6, F7 or F9, then the lemma holds.
From Claim 4.6, there exists i ∈ I such that the unique fat vertex of F is in Vf (Hi).
Then I ′ = {i} satisfies the hypotheses of Claim 4.7, and hence the lemma holds.
Claim 4.9. If F ∼= F1, then the lemma holds.
Let Vf (F ) = {f0, f1}. From Claim 4.6, there exist i0, i1 ∈ I such that fk ∈ Vf (Hik)
for each k = 0, 1. From Definition 1.2(ii), i0 6= i1. For each k = 0, 1, let sk be the unique
slim vertex of Hik . Since H is connected and 5 = m(F ) ≤ |Vs(H)|, there exist disjoint
subsets V0, V1 of Vs(H) such that |V0 ∪ V1| = 5, 〈〈Vk〉〉H is connected and sk ∈ Vk for
each k = 0, 1. Let V = V0∪V1. Then every vertex of V can be joined by a path in 〈〈V 〉〉H
to f0 or f1.
Suppose c(〈〈V 〉〉H) = 1, i.e., 〈〈V 〉〉H is connected. Let I ′ = {i ∈ I | Vs(Hi) ⊂
V }. Then |I ′| ≤ |V | = m(F ) and i0, i1 ∈ I ′. Since I ′ 6= ∅, H(I ′) is connected from
Lemma 3.9(i). Since i0, i1 ∈ I ′, Vf (F ) ⊂ Vf (H(I ′)). Hence I ′ satisfies the hypotheses of
Claim 4.7, and the lemma holds.
Next suppose c(〈〈V 〉〉H) > 1. Since 〈〈V0〉〉H and 〈〈V1〉〉H are connected, c(〈〈V 〉〉H) =
2. Since |V0| + |V1| = 5, we may assume |V0| ≥ 3 without loss of generality. Let s be
a slim vertex of 〈〈V0〉〉H which has the largest distance from s0. Then 〈〈V0 \ {s}〉〉H is
connected. Put K = 〈〈V \ {s}〉〉H . Then c(K) = 2. Moreover Vf (F ) ⊂ Vf (K), and
every vertex of V \ {s} can be joined by a path in K to f0 or f1. Hence G contains a con-
nected subgraph F ]K satisfying (4.1) by Lemma 4.3. Since |Vs(K)| = |V \ {s}| = 4,
the assumptions of Table 2 are satisfied. Hence the lemma holds.
Now we consider the remaining cases. Let F ′ be a subgraph of F such that{
F ′ ∼= F3 if F ∼= F2, F3, F5 or F8,
F ′ = F if F ∼= F4.
Obviously Vf (F ′) = Vf (F ). Hence F ′ = 〈〈Vs(F ′)〉〉F . Thus 〈V (F ′)∪V (H)〉G = F ′]H
from Lemma 3.7, i.e., F ′ ] H ⊂ G. Let f0 be the unique fat vertex of F ′ satisfying
|NsF ′(f0)| = 2, and let f1 be a fat vertex of F ′ different from f0. Then f0, f1 ∈ Vf (H(I))
from Claim 4.6.
Claim 4.10. If F ∼= F2, F3, F5 or F8, then the lemma holds.
T. Taniguchi: On graphs with the smallest eigenvalue at least −1−
√
2, part II 253
Then F ′ ∼= F3. From Lemma 3.9(i), H(I) is connected. If there is no edge between
NsH(I)(f0) and N
s
H(I)(f1), then the result follows from Lemma 4.1. Suppose that there
exist s0 ∈ NsH(I)(f0) and s1 ∈ N
s
H(I)(f1) such that s0 ∼ s1. For each k = 0, 1, there
exists ik ∈ I such that Vs(Hik) = {sk}. Put I ′ = {i0, i1}. By Lemma 3.9(i), H(I ′) is
connected. Then I ′ satisfies the hypotheses of Claim 4.7, and the lemma holds.
Claim 4.11. If F ∼= F4, then the lemma holds.
Let f2 be a fat vertex of F different from f0, f1. From Lemma 3.9(i), H(I) is con-
nected, and from Claim 4.6, Vf (F ) ⊂ Vf (H(I)). Put Ni = NsH(I)(fi) for i = 0, 1, 2.
If 〈N0 ∪ N1 ∪ N2〉H(I) is not connected, then the result follows from Lemma 4.2. Sup-
pose that 〈N0 ∪N1 ∪N2〉H(I) is connected. Then, for each i = 1, 2, there exists an edge
sis
(i)
0 between Ni and N0 such that si ∈ Ni and s
(i)
0 ∈ N0. Put I ′ = {i ∈ I | Vs(Hi) ⊂
{s(1)0 , s
(2)
0 , s1, s2}}. Since s
(1)
0 , s
(2)
0 , s1, s2 ∈ Vs(H(I)), 〈〈{s
(1)
0 , s
(2)
0 , s1, s2}〉〉H = H(I ′).
Since f0 is a common fat neighbour of s
(1)
0 and s
(2)
0 , s
(1)
0 and s
(2)
0 are adjacent, or equiv-
alently in H(I ′). Thus H(I ′) is connected. Then I ′ satisfies the hypotheses of Claim 4.7,
and hence the lemma holds.
The next three lemmas are verified by computer.
Lemma 4.12. Let F be a fat connected Hoffman graph satisfying the following conditions:
(i) |Vs(F )| = 2,
(ii) the two slim vertices of F are not adjacent,
(iii) |Vf (F )| ≤ 4,
(iv) every slim vertex has at most 2 fat neighbours,
(v) F is a non H -line graph.
Then F is isomorphic to F1, F3 or F4.
Lemma 4.13. Let F be a fat connected Hoffman graph satisfying the following conditions:
(i) 3 ≤ |Vs(F )| ≤ 4,
(ii) |Vf (F )| ≤ 2,
(iii) some slim vertex s of F has 2 fat neighbours,
(iv) some slim vertex s′ of F is not adjacent to s, and the others are adjacent to s,
(v) 〈〈Vs(F ) \ {s}〉〉F ∼= H3 or H5,
(vi) F is a non H -line graph.
Then F is isomorphic to F2, F5 or F8.
Lemma 4.14. Let F be a fat connected Hoffman graph satisfying the following conditions:
(i) 3 ≤ |Vs(F )| ≤ 6,
254 Ars Math. Contemp. 5 (2012) 243–258
(ii) |Vf (F )| = 1,
(iii) every slim vertex of F has 1 fat neighbour,
(iv) there exist different subsets V1 and V2 of Vs(F ) such that V1 ∪ V2 = Vs(F ), 〈〈V1〉〉F
and 〈〈V2〉〉F are isomorphic to H3 or H5, the vertex of Vs(F ) \ V2 and the vertex of
Vs(F ) \ V1 are adjacent to each other except some pair {s1, s2} (s1 ∈ Vs(F ) \ V2,
s2 ∈ Vs(F ) \ V1),
(v) F is a non H -line graph.
Then F contains a subgraph isomorphic to F6, F7 or F9.
We shall now prove our main result.
Proof of Theorem 1.5. From Proposition 2.1, the theorem holds if |V (Γ)| < 10. So we
prove that, if |V (Γ)| ≥ 10, then Γ has a subgraph isomorphic to one of the graphs in
Figure 2.
Since a complete graph and a cycle are H -line graphs, Γ is neither a complete graph
nor a cycle. Hence, from Lemma 3.3, there exists a non-adjacent pair {x, y} in V (Γ) such
that Γ−{x, y} is connected. Then Γ−x and Γ−y are connected as well. The graphs Γ−x,
Γ− y and Γ− {x, y} are H -line graphs by the minimality of Γ and |V (Γ− {x, y})| ≥ 8.
Let X =
⊎m1
i=0X
i (resp. Y =
⊎m2
i=0 Y
i) be a strict H -cover graph of Γ − y (resp.
Γ − x). Without loss of generality, we may suppose x ∈ Vs(X0) and y ∈ Vs(Y 0). From
Lemma 3.8, there exists a strict H -cover graph X̃ = X̃0](
⊎m1
i=1X
i) ofX−x. Similarly,
there exists a strict H -cover graph Ỹ = Ỹ 0](
⊎m2
i=1 Y
i) of Y −y. Obviously X̃ and Ỹ are
strict H -cover graph of Γ−{x, y}. From Theorem 31 of [11], there exists an isomorphism
ϕ : Ỹ → X̃ such that ϕ|(Γ−{x,y}) is the identity automorphism of Γ− {x, y}.
From Lemma 3.8, we can put X̃0 = X̃01 ] X̃02 ([X̃01 ], [X̃02 ] ∈ {[φ], [H2], [H3]}) and
Ỹ 0 = Ỹ 01 ] Ỹ 02 ([Ỹ 01 ], [Ỹ 02 ] ∈ {[φ], [H2], [H3]}), and put X = {φ, X̃01 , X̃02} and Y =
{φ, Ỹ 01 , Ỹ 02 }. Then X̃ = (
⊎
K∈X K) ] (
⊎m1
i=1X
i) = (
⊎
L∈Y ϕ(L)) ] (
⊎m2
j=1 ϕ(Y
j)).
From Lemma 3.6, {ϕ(L) | L ∈ Y} ∪ {ϕ(Y i) | 1 ≤ i ≤ m2} = X ∪ {Xi | 1 ≤ i ≤ m1}.
Put Z = X ∪ {ϕ(L) | L ∈ Y}. Then
X̃ = (
⊎
Z∈Z
Z) ]H, (4.8)
where
H =
⊎
i∈I
Xi =
⊎
j∈J
ϕ(Y j) (4.9)
for some I ⊂ {1, 2, . . . ,m1} and J ⊂ {1, 2, . . . ,m2}. Obviously
X = X0 ] (
⊎
Z∈Z\X
Z) ]H, Y = Y 0 ] (
⊎
Z∈Z\{ϕ(L)|L∈Y}
ϕ−1(Z)) ] ϕ−1(H), (4.10)
Claim 4.15. The graph H is connected.
Since Γ − {x, y} is connected, so is X̃ . The Hoffman graph H ′ =
⊎
Z∈Z Z has the
unique fat vertex α satisfying Vf (H ′) ∩ Vf (H) = {α} and NsH′(α) = Vs(H ′). Using
Lemma 3.1 on the decomposition (4.8), We conclude that H is connected.
T. Taniguchi: On graphs with the smallest eigenvalue at least −1−
√
2, part II 255
We define the edge set
E0 =
 ⋃
z∈Vs(X0)
{zf | f ∈ Vf (H) ∩NfX0(z)}
∪
 ⋃
z∈Vs(Y 0)
{zϕ(g) | g ∈ Vf (ϕ−1(H)) ∩NfY 0(z)}

and the Hoffman graph
G = (V (Γ) ∪ Vf (H), E(Γ) ∪ E(H) ∪ E0).
Let
F = 〈〈Vs(X0) ∪ Vs(Y 0)〉〉G.
Obviously the following holds:
s ∈ Vs(F ), f ∈ Vf (G), sf ∈ E(G) =⇒ sf ∈ E0, (4.11)
and
(a) Vf (F ) ⊂ Vf (H), (b) E0 ⊂ E(F ), (c) Γ ⊂ G and Vs(Γ) = Vs(G).
(4.12)
Also, from (4.8),
(a) Vs(Γ) = Vs(F ) ∪ Vs(H), (b) Vs(F ) ∩ Vs(H) = ∅. (4.13)
From (4.13),
|Vs(H)| ≥ 10− |Vs(F )|. (4.14)
By the definition of G,
Vf (G) = Vf (H). (4.15)
Claim 4.16. G = F ]H .
Let us check the conditions (i)–(iv) of Definition 1.2.
From (4.12)-(c) and (4.13)-(a), Vs(G) = Vs(F ) ∪ Vs(H). Moreover, it is Vf (G) =
Vf (H) = Vf (F ) ∪ Vf (H) by (4.12)-(a) and (4.15). Hence the condition (i) is satisfied.
Also, by (4.13)-(b), the condition (ii) is satisfied. By the definitions of F and G, the condi-
tion (iii) is satisfied.
Let s1 ∈ Vs(F ), and let s2 ∈ Vs(H). Then s1 ∈ Vs(X0) or s1 ∈ Vs(Y 0), s2 ∈
Vs(H) ⊂ Vs(
⊎m1
i=1X
i). By (4.15), NfG(s2) = N
f
H(s2). First suppose s1 ∈ Vs(X0). Since
NfH(s2) ⊂ Vf (H), N
f
G(s1) ∩ N
f
G(s2) = (N
f
X0(s1) ∩ Vf (H)) ∩ N
f
H(s2) = N
f
X0(s1) ∩
NfH(s2). Since N
f
X0(s1) = N
f
X(s1) and N
f
H(s2) = N
f
X(s2), N
f
G(s1) ∩ N
f
G(s2) =
NfX(s1) ∩ N
f
X(s2). Thus, s1 and s2 have at most one common fat neighbour in G, and
they have one if and only if they are adjacent in X , or equivalently in G. Hence (iv) holds
in this case. Next suppose s1 ∈ Vs(Y 0). Since s2 ∈ Vs(H), s2 ∈ ϕ(Vs(Y j)) for some
256 Ars Math. Contemp. 5 (2012) 243–258
j ∈ {1, 2, . . . ,m2}. Hence NfG(s2) = N
f
H(s2) = N
f
ϕ(Y j)(s2) = N
f
ϕ(Y j)(ϕ(s2)) =
ϕ(NfY j (s2)) = ϕ(N
f
Y (s2)). Thus
NfG(s1) ∩N
f
G(s2) = ϕ(Vf (ϕ
−1(H)) ∩NfY 0(s1)) ∩ ϕ(N
f
Y (s2))
= ϕ(NfY (s1) ∩N
f
Y (s2) ∩ Vf (ϕ
−1(H)))
= ϕ(NfY (s1) ∩N
f
Y (s2))
since ϕ−1(H) ⊂ Y . A similar argument shows that (iv) holds in this case as well.
Claim 4.17. For any s ∈ Vs(F ),
|NfG(s)| ≤
{
|Vf (X0)| if s ∈ Vs(X0),
|Vf (Y 0)| otherwise.
By (4.11), sf ∈ E0 for each f ∈ NfG(s). Suppose s ∈ Vs(X0). Then sf ∈ E(X0).
Hence |NfG(s)| ≤ |N
f
X0(s)| ≤ |Vf (X
0)|. Suppose s ∈ Vs(Y 0). Then sϕ−1(f) ∈ E(Y 0).
Hence |NfG(s)| ≤ |N
f
Y 0(s)| ≤ |Vf (Y
0)|.
Claim 4.18. |Vf (F )| ≤ |Vf (X0)|+ |Vf (Y 0)|.
From Claim 4.16, Vf (F ) = Vf (〈〈Vs(X0) ∪ Vs(Y 0)〉〉F]H). By (4.12)-(a), Vf (F ) =
Vf (〈〈Vs(X0) ∪ Vs(Y 0)〉〉F]H) ∩ Vf (H), i.e.,
Vf (F ) =
(
Vf (X
0) ∩ Vf (H)
)
∪
(
ϕ(Vf (Y
0) ∩ ϕ−1(Vf (H)))
)
.
Hence
|Vf (F )| ≤ |Vf (X0) ∩ Vf (H)|+ |Vf (Y 0) ∩ ϕ−1(Vf (H))|
≤ |Vf (X0)|+ |Vf (Y 0)|.
Claim 4.19. The Hoffman graph F is a non H -line graph.
The Hoffman graphH is a strict H -cover graph of itself. Suppose that F is an H -line
graph. Then there exists a strict H -cover graph of F (cf. Example 22 of [11]). Hence G
has a strict H -cover graph from Lemma 20 of [11]. Since Γ ⊂ G, Γ is an H -line graph,
a contradiction.
Claim 4.20. If X0 or Y 0 is isomorphic to H2, the theorem holds.
IfX0 or Y 0 is isomorphic toH2, then Vs(X0)∩Vs(Y 0) = ∅, and each slim vertex of F
has at most 2 fat neighbours by Claim 4.17. First suppose thatX0 and Y 0 are isomorphic to
H2. Then |Vs(F )| = |{x, y}| = 2 and |Vf (F )| ≤ 4 by Claim 4.18. Hence the hypotheses
of Lemma 4.12 hold by Claim 4.19. Thus F ∼= F1, F3 or F4, and |Vs(H)| ≥ 8 by (4.14).
Next suppose otherwise. Then 3 ≤ |Vs(F )| = |Vs(X0) ∪ Vs(Y 0)| ≤ 4, and |Vf (F )| ≤ 3
by Claim 4.18. If |Vf (F )| = 3, then Vf (X0) ∩ Vf (Y 0) = ∅, and therefore F is an H -
line graph since Vs(X0) ∩ Vs(Y 0) = ∅, a contradiction to Claim 4.19. Obviously the
hypotheses (v) and (iv) of Lemma 4.13 hold. Hence the hypotheses of Lemma 4.13 hold
by Claim 4.19. Thus F ∼= F2, F5 or F8, and |Vs(H)| ≥ 6 by (4.14). Hence the theorem
holds from Lemma 4.4 if X0 or Y 0 is isomorphic to H2.
T. Taniguchi: On graphs with the smallest eigenvalue at least −1−
√
2, part II 257
For the remainder of this proof, we assume thatX0 and Y 0 are isomorphic toH3 orH5.
Then 3 ≤ |Vs(X0) ∪ Vs(Y 0)|(= |Vs(F )|) ≤ 6. Hence the condition (i) of Lemma 4.14
holds. Suppose Vf (X0) ∩ ϕ(Vf (Y 0)) = ∅. Then Vf (X̃0) ∩ Vf (ϕ(Ỹ 0)) = ∅. Hence
V (X̃0)∩V (ϕ(Ỹ 0)) = ∅ by (4.8) since X̃ = ϕ(Ỹ ). Thus Vs(X0)∩Vs(Y 0) = ∅, and there-
fore F = 〈〈Vs(X0)∪Vs(Y 0)〉〉G = 〈〈Vs(X0)〉〉G]〈〈Vs(Y 0)〉〉G. Obviously 〈〈Vs(X0)〉〉G
and 〈〈Vs(Y 0)〉〉G are isomorphic to H3 or H5. Hence F is an H -line graph. But this con-
tradicts Claim 4.19. Thus Vf (X0) ∩ ϕ(Vf (Y 0)) 6= ∅, i.e., ϕ maps the unique fat vertex of
Y 0 to the unique fat vertex of X0, and |Vf (F )| = 1. Hence the conditions (ii) and (iii) of
Lemma 4.14 hold. Moreover the condition (v) of Lemma 4.14 holds by Claim 4.19.
Put V1 = Vs(X0) and V2 = Vs(Y 0), and put s1 = x and s2 = y. Then
• (Vs(F )\V2)\{s1} = Vs(X̃0)\Vs(Y 0) ⊂ Vs(
⊎
Z∈Z\{ϕ(L)|L∈Y} ϕ
−1(Z)) by (4.10),
• Vs(F ) \ V1 = Vs(Y 0) \ Vs(X0) ⊂ Vs(Y 0),
• (Vs(F ) \ V1) \ {s2} = Vs(Ỹ 0) \ Vs(X0) ⊂ Vs(
⊎
Z∈Z\X Z) by (4.10),
• Vs(F ) \ V2 = Vs(X0) \ Vs(Y 0) ⊂ Vs(X0).
Hence the vertex of Vs(F ) \ V2 and the vertex of Vs(F ) \ V1 are adjacent to each other
except the pair {s1, s2} (s1 ∈ Vs(F ) \ V2, s2 ∈ Vs(F ) \ V1). Thus the conditions (iv) of
Lemma 4.14 holds. Therefore F has a subgraph isomorphic to F6, F7 or F9. Let F ′ be a
subgraph isomorphic to F6, F7 or F9, of F . Then F ′ ] H ⊂ G from Lemma 3.7. Now
|Vf (F ′)| = 1, |Vs(H)| ≥ 4 by (4.14). Moreover Vf (F ′) = Vf (F ) ⊂ Vf (H) from (4.12)-
(a). Hence the hypothesis of Lemma 4.4 is satisfied. Thus F ′ ] H has a slim subgraph
isomorphic to one of the graphs in Figure 2, and so does G.
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 H. Sachs, Spectra of Graphs – Theory and Applications, III revised
and enlarged edition, Johan Ambrosius Bart. Verlag, Heidelberg - Leipzig, 1995.
[3] D. Cvetković, M. Doob and S. Simić, Generalized line graphs, J. Graph Theory 5 (1981),
385–399.
[4] D. Cvetković, M. Lepović, P. Rowlinson and S. K. Simić, The maximal exceptional graphs,
J. Combin. Theory Ser. B 86 (2002), 347–363.
[5] D. Cvetković, P. Rowlinson and 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] D. Cvetković, P. Rowlinson and S. K. Simić, Spectral Generalizations of Line Graphs — On
Graphs with Least Eigenvalue −2, Cambridge Univ Press, 2004.
[7] A. J. Hoffman, On graphs whose least eigenvalue exceeds −1−
√
2, Linear Algebra Appl. 16
(1977), 153–165.
258 Ars Math. Contemp. 5 (2012) 243–258
[8] L. Lovász, Combinatorial Problems and Exercises, 2nd edition, North-Holland, 1993.
[9] The Magma Computational Algebra System for Algebra, Number Theory and Geometry, URL:
http://magma.maths.usyd.edu.au/magma/
[10] B. D. McKay, Combinatorial Data, URL: http://cs.anu.edu.au/˜bdm/data/
graphs.html
[11] T. Taniguchi, On graphs with the smallest eigenvalue at least −1 −
√
2, part I, Ars Math.
Contemp. 1 (2008), 81–98.
[12] R. Woo and A. Neumaier, On graphs whose smallest eigenvalue is at least −1 −
√
2, Linear
Algebra Appl. 226/228 (1995), 577–591.