ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 555-579 https://doi.org/10.26493/1855-3974.1581.b47
(Also available at http://amc-journal.eu)
On graphs with the smallest eigenvalue at least -1 - V2, part III
Tetsuji Taniguchi t
Hiroshima Institute of Technology, Department of Electronics and Computer Engineering, 2-1-1 Miyake, Saeki-ku, Hiroshima, Japan
Received 15 January 2018, accepted 13 September 2019, published online 3 December 2019
There are many results on graphs with the smallest eigenvalue at least -2. In order to study graphs with the eigenvalues at least -1 - %/2, R. Woo and A. Neumaier introduced Hoffman graphs and H-line graphs. They proved that a graph with the sufficiently large minimum degree and the smallest eigenvalue at least -1 - a/2 is a slim {[h2], [hs], [hr], [h9]}-line graph. After that, T. Taniguchi researched on slim {[h2], [hs]}-line graphs. As an analogue, we reveal the condition under which a strict {[hi], [h4], [h7]}-cover of a slim {[hr]}-line graph is unique, and completely determine the minimal forbidden graphs for the slim {[hr]}-line graphs.
Keywords: Hoffman graph, line graph, smallest eigenvalue. Math. Subj. Class.: 05C50, 05C75
*S. K. was supported by JSPS KAKENHI; grant number: 18J10656. tT. T. was supported by JSPS KAKENHI; grant number: 16K05263.
E-mail addresses: kubota@ims.is.tohoku.ac.jp (Sho Kubota), t.taniguchi.t3@cc.it-hiroshima.ac.jp (Tetsuji Taniguchi), kiyoto.yosino.r2@dc.tohoku.ac.jp (Kiyoto Yoshino)
Sho Kubota *
Tohoku University, Graduate School of Information Sciences, 6-3-09 Aoba, Aramaki-aza Aoba-ku, Sendai, Miyagi, Japan
*
Kiyoto Yoshino
Tohoku University, Graduate School of Information Sciences, 6-3-09 Aoba, Aramamaki-aza, Aoba-ku, Sendai, Miyagi, Japan
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
556
Ars Math. Contemp. 17 (2019) 493-514
1 Introduction
Throughout this paper, we will consider only undirected graphs without loops or multiple edges, and denote by Amin(T) and ¿(r) the minimum eigenvalue and the minimum degree of a graph r, respectively.
P. J. Cameron, J. M. Goethals, J. J. Seidel and E. E. Shult have characterized generalized line graphs as the graphs with the smallest eigenvalue at least —2 except for finitely many graphs with at most 36 vertices in [3]. After that, A. Hoffman proved the following theorem in [6].
Theorem 1.1. There exists an integer valued function f defined on the intersection of the half-open interval (-1 — a/2, -2] and the set of the smallest eigenvalues of graphs, such that if r is a connected graph with ¿(r) > f (Amin(r)) then
(i)	if — 1 > Amin(r) > —2 then r is a complete graph and Amin(r) = —1.
(ii)	if—2 > Amin(r) > —1 — a/2 then r is a generalized line graph and Amin(r) = —2.
In [12], R. Woo and A. Neumaier introduced Hoffman graphs and H-line graphs, where H is a family of isomorphism classes of Hoffman graphs, to extend the result of A. Hoffman, and proved Theorem 1.2. Moreover, they raised the problem [12, Open problem 3] to reveal the list of minimal forbidden graphs for the slim {[h2], [hs], [hr], [h9]}-line graphs. These Hoffman graphs and some ones that appear in this paper and [12] are listed in Figure 1 (here, the names hi, h2,... depend on [12]).
hi
h2
A -V
h4 =
r=
• • hs = • h6 = •• = Xlj
Figure 1: Hoffman graphs with slim (resp. fat) vertices depicted as small (resp. large) black dots.
Theorem 1.2. Let a4 (« —2.4812) be the smallest root of the polynomial x3 + 2x2 — 2x — 2. There exists an integer valued function f defined on the intersection of the half-open interval (a4, —1 — a/2] and the set of the smallest eigenvalues of graphs, such that if r is a graph with Amin(r) G (a4, —1 — a/2] and ¿(r) > f (Amin(r)), then r is an {[h2], [hs], [hr], [ho]}-line graph.
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
557
Since it is difficult to solve the open problem, T. Taniguchi considered a partial problem. In [11], he completely determined the 38 minimal forbidden graphs for the slim {[h2], [hs]}-line graphs by using Theorem 1.3 [10].
Theorem 1.3. A slim {[h2], [hs]}-line graph with at least 8 vertices has a unique strict {[h2], [h3], [hs]}-cover up to equivalence.
As an analogue of his result, we reveal the minimal forbidden graphs for the slim {[hr] }-line graph. In Section 2, we introduce a part of the basic theory of Hoffman graphs summarized in detail in [7]. In Section 3, we introduce minimal forbidden graphs. In Section 4, we aim to prove Theorem 4.11 which reveals the necessary and sufficient condition that a strict {[hi], [h4], [hr]}-cover of a slim {[hr]}-line graph becomes unique up to equivalence. Furthermore, when the condition is not satisfied, the theorem shows the shape of the slim {[hr]}-line graph and indicates its strict {[h1], [h4], h]}-covers are exactly two up to equivalence. This helps us to examine the minimal forbidden graphs for the slim {[hr]}-line graphs. In order to prove our main result Theorem 5.1, in which we determine the minimal forbidden graphs for the slim {[hr]}-line graphs, we computed the minimal forbidden graphs with at most 9 vertices by the software Mamga [2]. In Section 5, we determine the minimal forbidden graphs apart from those with at most 9 vertices.
2 Hoffman graphs
We introduce definitions related to Hoffman graphs. Details are in [7].
Definition 2.1. A Hoffman graph h is a pair (H, m) of a graph H = (V, E) and a labelling map m: V ^ {f, s}, satisfying the following conditions:
(i)	every vertex with label f is adjacent to at least one vertex with label s;
(ii)	vertices with label f are pairwise non-adjacent.
We call a vertex with label s a slim vertex, and one with label f a fat vertex. We denote by Vs(h) (resp. Vf (h)) the set of slim (resp. fat) vertices of h.
For a vertex x of a Hoffman graph h, we denote by Nf (x) (resp. Nj®(x)) the set of neighbors labelled f (resp. s) of x, and set N (x) = Nf (x) U N^x). For a set X of vertices of h, we let Nf (X) := |JxeX Nf (x) and N^X) := |JN^x). We regard an ordinary graph H without labelling as a Hoffman graph (H, m) without fat vertices, that is, m(x) = s for any vertex x of H. Such a graph is called a slim graph.
Definition 2.2. A Hoffman graph h' = (H', m') is called an induced Hoffman subgraph of a Hoffman graph h = (H, m), if H' is an induced subgraph of H and m|V(H') = m'. For a subset S of Vs(h), we denote by ((S}}(, the induced Hoffman subgraph of h by SU Nf (S).
We denote by (S}r the ordinary induced subgraph by S of a graph r for a subset S of V(r). For a Hoffman graph h, (Vs(h)}h is called the slim subgraph of h. The diameter of a graph is the maximum distance between two distinct vertices. Let r be a graph and C be a subset of V(r). Then, C is a clique in r if the induced subgraph (C}r is a complete graph. The size of the largest clique in r is called the clique number. A partition n = {C1, C2,..., Ct} of V(r) is called a clique partition if all cells Cj are cliques. Focusing on cliques is useful for discovering the structure of line graphs. Also in this paper, we may focus on clique numbers and clique partitions.
558
Ars Math. Contemp. 17 (2019) 493-514
Definition 2.3. Let h be a Hoffman graph, and let h1 and h2 be two induced Hoffman subgraphs of h. The Hoffman graph h is said to be the sum of h1 and h2, written as h = h1 ® h2, if the following conditions are satisfied:
(i)	V(h) = V(h1) u V(h2);
(ii)	Vs(h) = Vs(h1) u Vs(h2) and Vs(h1) n Vs(h2) = 0;
(iii)	if x e Vs(hi), y € Vf (h) for i = 1 or 2, and x ~ y, then y e Vf (h®);
(iv)	if x e Vs (h1) and y e Vs (h2), then x and y have at most one common fat neighbor, and they have one if and only if they are adjacent.
If h is the sum of some two nonempty Hoffman graphs, then it is said to be decomposable. Otherwise, h is said to be indecomposable.
Remark that the sum of Hoffman graphs satisfies commutative and associative laws.
Definition 2.4. Let h and m be Hoffman graphs, and let ^ be a graph morphism from the underlying graph of h to that of m. Mapping ^: h ^ m is called a morphism if it preserves the labelling, that is, ^(Vs(h)) C Vs(m) and ^(Vf (h)) C Vf (m). If ^ is a morphism and a graph isomorphism, then it is called an isomorphism, and h and m are said to be isomorphic, written as h — m. Let [h] denote the isomorphism class of h.
Definition 2.5. Let H be a family of isomorphism classes of Hoffman graphs. A Hoffman graph m is called a H-line graph if it is an induced subgraph of some Hoffman graph h = 0"=1 h®, where [h®] € H for every i. In this case, m is called a slim H-line graph if m is a slim graph, and h is called a strict H-cover of a graph r if Vs(h) = V(r). Two strict H-covers h and h' of a graph r are said to be equivalent, if there exists an isomorphism ^: h ^ h' such that ^>|r is the identity automorphism of r.
Lemma 2.6. Let H be a family of isomorphism classes of Hoffman graphs, and let H' be the family of the isomorphism classes of indecomposable induced Hoffman subgraphs by a nonempty set of slim vertices in a member of H. Then, every slim H-line graph has a strict
H'-cover.
Proof. Let h = 0"=1 h®, where [h®] € H for every i. Then, it holds that
n
«S»h = 0 ((S n Vs(h®)»h
®=1
forasubset S of Vs(h). Therefore ((S}}^ isastrict H'-cover of the induced subgraph by S since every addend is the sum of some indecomposable induced Hoffman graphs of h. □
3 Minimal forbidden graphs
In graph theory, various important families of graphs can be described by a set of graphs that do not belong to that family. This is the concept of so-called minimal forbidden graphs. First, we give the definition. Suppose that a family G of graphs is closed under the operation to take induced subgraphs, that is, G satisfies the condition that for a graph G in G, any induced subgraph of G is also in G. Then, we say that a graph F is a minimal forbidden graph for G if both of the following are satisfied:
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
559
(i) F is not in G;
(ii) Every proper induced subgraph of F is in G.
On the family of ordinary line graphs [1] and the family of slim {[h2], [hs]}-line graphs [11], their minimal forbidden graphs are revealed. Besides this, characterizations of forests, perfect graphs [4] and Threshold graphs [5] by minimal forbidden graphs are also known. In addition, Sumner [9] claimed that if r is a connected K1j3-free graph of even order, then r has a 1-factor. As such, there are also known results that properties of a family of graphs in the case that "forbidden graphs" are specified in advance. As we can see from these results, revealing the minimal forbidden graphs is one way to understand families of graphs. Unfortunately not being finite, but we are able to reveal the minimal forbidden graphs for the slim {[hr]}-line graphs.
4 The condition that an {[hi], [h4], [h7]}-strict cover of a slim {[h7]}-line graph is unique up to equivalence
In this section, set H = {[h1], [h4], [hr]}. Note that every slim {[hr]}-line graph has a strict H-cover by Lemma 2.6. For exmaple, the graph r in Figure 2 is a slim {[hr]}-line graph. Indeed, considering the sum h = h7 ® h1 ® h4 of Hoffman graphs in Figure 9, we see that
r
h = hr e hi e h4 =
Figure 2: A slim {[hr]}-line graph and its strict {[h1], [h4], [h7]}-cover.
the slim subgraph of h is the graph r. (In Figure 2, the dotted lines are used for convenience to show what kind of small Hoffman graphs the graph r is decomposed by. In addition, for two vertices x and y which belong to distinct addends, we omit the edge between x and y if they have a common fat neighbor since the existence of edge between x and y depends only on that of their common fat neighbor by Definition 2.3 (iv).) In addition, h 1 and h4 are induced subgraphs of hr, so the graph r is certainly a slim {[hr]}-line graph. On the other hand, since Vs(h) = V(T) holds, the Hoffman graph h is a strict {[h1], [h4], [h7]}-cover of r.
Let h = 0n=1 h® where [h®] € H for every i. Then, we can regard Nf as a mapping from Vs (h) to Vf (h) since every slim vertex is adjacent to exactly one fat vertex. For a slim vertex x of h, let h(x) denote the addend h® containing x, and let C\(x) = N^(Nf (x))
560
Ars Math. Contemp. 17 (2019) 493-514
and
cov h := IN» | u e Vf (h)} = {Ch(x) | x e Vs(h)}.
Let x be a slim vertex of h. We show that C, (x) is a clique. First, we take u e Vf (h) such that Nf ( x) = {u}. We arbitrarily take two slim vertices y and z in NS(u) (= C, (x)). It suffices to show that y and z are adjacent. If y and z are contained in the same indecomposable addend of h, then they are adjacent. Otherwise, so are they by Definition 2.3 (iv). Hence, the desired result follows. Note that cov h is a clique partition of Vs (h). Moreover, it holds clearly that Nf | a =	for any subset A c Vs (h).
Lemma 4.1. Let h = 0"=1 hl> where [h®] e H for every i, and let C be a clique of the slim subgraph of h. Then, the following hold:
(i)	two distinct slim vertices x and y are adjacent if and only if h(x) = h(y) or Nf (x) = Nf (y);
(ii)	C c C, (x) for any x e C, or C c Vs(h(y)) for any y e C;
(iii)	If C c Ch (x) n Vs(h(y)) for some x,y e C, then |C| < 2.
Proof. Statements (i) and (iii) hold clearly. Assume that C C C, (x) for some x e C. There exists y e C such that Nf (x) = Nf (y). Thus, h(x) = h(y) holds by (i). Statement (ii) follows since Nf (x) = Nf (z) or Nf (x) = Nf (z) for each z e C.	□
We introduce some definitions to determine the strict H-covers of a graph.
Definition 4.2. Let r be a graph, and let {Cj}ie/ be a partition of the vertex set of r. Then, define n(x) = Nr(x) — C® for x e C®. In addition, define n0(x) = {x} and
nk (x) = nk-1(x) U J n(y)
yGnk—1 (x)
for a positive integer k. A vertex x of r is said to be good for the given partition {Cj}ie/ if x satisfies one of the following conditions:
(i)	n(x) = 0;
(ii)	n(x) = {y} for some y, and n(y) = {x};
(iii)	n(x) = {y, z} for some y and z, n(y) = {x}, n(z) = {x}, and y ~ z;
(iv)	n(x) = {y} for some y, n(y) = {x, z} for some z, n(z) = {y}, and x ~ z.
Furthermore, a set of vertices is said to be good if every element is good. Let Or be the set of clique partitions for which every vertex is good.
We can regard cov as a mapping from the set of equivalent classes of strict H-covers of r to Or, and Proposition 4.3 holds. It is clear that if n(u) has a good vertex then u is good, and if u is good then n(u) is good.
Proposition 4.3. The mapping cov for a graph is bijective.
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
561
Proof. We construct the inverse mapping of cov. Let {Ci}iei G Or. A Hoffman graph m is defined as Vs(m) := V(r), Vf (m) := {Ci}iej and
E(m) := E(r) U {{x, C} | x G V(r), and C G {CJie/ and x G C}.
For x G V(r), define the induced Hoffman graph mx := ((n2(x)))m. It holds that
m = 0{mx | x G V(r)}, and
[mx] = [hi], [h4] or [hr] for each vertex x.
Hence, m is a strict H-cover of r. The mapping
^: Or 3 {Ci}ie/ ^ m G the set of strict H-covers of r
is the inverse mapping of the mapping cov.	□
We have the following lemma:
Lemma 4.4. Let r be a graph with a partition {Ci}ie1 of the vertex set. Then, a vertex x is good for {Ci}ie/ if and only if x is good for {n3(u) n Ci}ie/ in (n3(u))r.
Let r be a connected graph, and let K be a nonempty set of vertices. Then, let
dKr(x) = dK (x) = d(x) := min d(x, k) '	keK
for x G V(r), where d(x, y) is the distance between x and y. Define
dmax = max dK,r(y), yev(r) '
and let (K) denote the family
{{y G{x}U N(x) | dK,r(y) > 0K,r(x)} | x G V(r) and dK,r(x) G 2N + 1} U {K}
of sets of vertices. If K g cov h then ^r(K) = cov h for every strict H-cover h of r. This means that we can restore the clique partition if we find a member of a partition in Or. We have the following lemmas:
Lemma 4.5. Let r be a graph with a clique K. If (K) is a partition of V(r) and r has no induced subgraph isomorphic to K1,3, then ^r(K) is a clique partition.
Lemma 4.6. Let r be a connected slim {[hr] }-line graph with a clique C of size c. Let h be a strict H-cover of r. If the following (i) or(ii) holds, then C (x) is the maximal clique containing C for any x G C, and a strict H-cover of r is unique up to equivalence.
(i)	c > 4,
(ii)	c = 3, and |Nm (C)| = 1 for any strict H-cover m of r.
Proof. In the case of (i), for each clique D which contains C and any x G C, D C C (x) holds by Lemma 4.1 (ii) and | D | > 4. Hence, C^ (x) is a unique maximal clique containing C for any x G C .In the case of (ii), we can prove as well by Lemma 4.1 (ii) and (iii).
Next, we show the uniqueness of a strict H-cover of r. The maximal clique D containing C is defined independently of a choice of a strict H-cover. Hence, ^r(D) is also defined independently of one. By Proposition 4.3, a strict H-cover of r is unique. □
562
Ars Math. Contemp. 17 (2019) 493-514
We define
Si
and
S2
Lemma 4.7. Let h be a strict H-cover of a graph r. If r has an induced subgraph isomorphic to Si or S2, then the vertices of the triangle of the induced subgraph are adjacent to the same fat vertex in h.
Proof. Let A be the triangle in the induced subgraph S ~ Si or S2. Let m be a strict H-cover of r. We suppose that |N*m(A)| > 2 to prove INÎ(A)| = 1 by contradiction. Then, we have A is not contained in Cm(x) for every x G V(r) since every slim vertex in Cm (x) are adjacent to the same fat vertex. This together with Lemma 4.1 (ii) implies that
A c Vs(m(y)) for any y G A.
We take a vertex y G V(A). Then, A c Vs(m(y)), and hence [m(y)] ((V(S)}}m is a strict H-cover of S. Hence, we have
[hr]. Moreover,
((V(S)»m = ((A»m(tf) ©((V(S) \ A))m/ ^ hr ©((V(S) \ A))m',
where m' denotes the Hoffman graph so that m = m(y) © m'. It is easy to verify that the slim subgraph of hr © ((V(S)))m/ is distinct from Si and S2. This is a contradiction to S ~ S1 or S2. Therefore the desired result follows.	□
The Lemma 4.6 gives conditions that a strict H-cover is unique, and Lemma 4.7 gives a concrete situation satisfying one of the conditions.
Lemma 4.8. If the slim subgraph of a Hoffman graph h = 0N=1 h® with [h®] € H for every i is connected, then that of 0 i=1 ®=k h® is connected for some k.
Proof. Note that an {[hr]}-line graph is connected if and only if the slim subgraph is connected. Let r be the graph with the vertices {1,..., N} whose two distinct vertices x and y are adjacent if and only if V (h®) n V (hj) = 0. Since r is connected, there exists integer k such that r - k is also connected. Hence, 0N=1 ®=k h® is connected, and the slim subgraph is connected.	□
Let t = (ii)n=1 be a finite sequence of positive integers. Then, define the graphs Pt and
Ct by
V (Pt) = V (Ct) E (Pt) E (Ct)
{(i,j) | 1 < i < n, 1 < j < ti},
{{(i, j), (i', j')} I i - i' = 1, or i = i' and j = j'},
{{(i, j), (i', j')} I i - i' = 1 (mod n), or i = i' and j = j'},
respectively (see Example 4.10). Let
K,...,afc ] := {(a,,j ) G V (r) | 1 < i < k, 1 < j < ta.}
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
563
for jai,..., ak} C {1,..., n}, where r = Pt or Ct. In addition, let
TP := {(ti)"=i G{1, 2}n | n e Z>2,ti + ti+i < 3(1 < Vi < n - 1)} and (4.1) TC := {(ti)n=i e {1, 2}n | n e (2Z)>4, t» +t(i+1 mod n) < 3(1 < Vi < n)}. (4.2)
Furthermore, a vertex u of a graph is said to be end if the graph is isomorphic to Pt for some t e TP with the length n, and u e [1] or [n]. In the following lemma, we see that Pt and Ct are slim {[hr] }-line graphs, and reveal their strict H-covers.
Lemma 4.9. For t e TP of length n, we have OPt is the set of
{[1], [2, 3], [4, 5], [6, 7],...} and {[1, 2], [3,4], [5, 6],...}.	(4.3)
For t e CP of length n, we have OCt is the set of
{[1, 2], [3,4],..., [n - 1, n]} and {[n, 1], [2, 3],..., [n - 2, n - 1]}. (4.4)
Namely, for t e TP (resp. TC), the graph Pt (resp. Ct) has precisely two strict H-covers up to equivalence.
Proof. Recall that ^r(C) = n holds for every C e n where r is a slim {[hr]}-line graph and n e Or. In order to reveal Or, it suffices to verify whether (K) is in Or for every clique K of r.
We fix a sequence t e TP of length n, and determine OPt. Since if n = 2 then desired result holds, we may assume that n > 3. On the other hand, every clique of Pt is contained in [i, i + 1] for an integer i e {1,..., n - 1}. The clique partitions in (4.3) are obtained from cliques [1], [n] and [i, i + 1] for i e {1,..., n - 1}. Moreover we can verify that (K) is not in OPt for one clique K of the other following cliques:
(i)	non-empty subsets of [i] for i e {2,..., n - 1};
(ii)	{(i, 1), (i + 1,1)} and {(i, 2), (i + 1,1)} for i e {1,..., n - 1} with t» = 2;
(iii)	{(i, 1), (i + 1,1)} and {(i, 1), (i + 1, 2)} for i e {1, ...,n - 1} with t»+i = 2.
Similarly, we can determine OCt for every t e TC. Finally, by Proposition 4.3, which claims that cov is a bijection from the set of strict H-cover of a slim {[hr] }-line graph r to Or, Pt and Ct have precisely two strict H-covers up to equivalence.	□
Example 4.10. We give examples of strict H-covers of Pt and Ct. In the case of t =
564	Ars Math. Contemp. 17 (2019) 493-514
By Proposition 4.3, these clique partitions give strict H-covers. They are
and ■
respectively. The similar consideration is applied to Ct for t g TC. For example, we consider t = (1,1, 2,1,2,1). Then the graph Ct is
and
By Proposition 4.3, we have the following two strict H-covers:
and
Theorem 4.11. If a connected slim {[h7]}-line graph r with the clique number c satisfies one of the following conditions:
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
565
(a)	c =1 or c > 4;
(b)	r has an induced subgraph isomorphic to S1
or S2

then it has a unique strict {[hi], [h4], [h7]}-cover up to equivalence. Otherwise, r is isomorphic to Pt for some t e TP or Ct for some t e TC, and it has precisely two strict {[hi], [h4], [hr]|-covers up to equivalence.
Proof. If (a) or (b) holds then a strict H-cover is unique by Lemma 4.6 and Lemma 4.7 (see Example 4.12). Otherwise, it is proved that r is isomorphic to either Pt for some t G TP or Ct for some t e TC by induction on the number of addends of a strict H-covers of r. Fix a strict H-cover h = 0 N=1 h®, where [h®] G H for every ¿.If N =1 then r ~ P{i,i} or P{1,2}. Otherwise, we can take an integer k such that the subgraph r' induced by the slim vertices of h' = 0N=1 ®=k h® is connected by Lemma 4.8. Each of S1 and S2 is not isomorphic to any induced subgraph in r'. Note that the clique number c' of r' is at most 3. Suppose c' = 2 or 3 since the result follows if c' = 1.
h = h' ® hk = mj ® hk
The slim subgraph of h
k
h
Figure 3: An example of the case that the slim subgraph of h' is isomorphic to Ct for
t e TC.
If r' ~ Ct/ for some t' e TC, then h = h' ® hk must have an induced subgraph isomorphic to either S1 or S2 (see Figure 3). Otherwise, r' ~ Pt> for some t' e TP. Let
mi := cov-1({[1], [2, 3], [4, 5], [6, 7],...}), m2 := cov-1({[1, 2], [3, 4], [5, 6],...}),
and let n denote the length of t. By the induction hypothesis, we can take j e {1, 2} so that h' and mj are equivalent. Then, we show that the following two conditions hold:
(A) |Nm (u)| + |NSk (u)| < 3 holds for every u e Vf (mj) n Vf (hk);
566
Ars Math. Contemp. 17 (2019) 493-514
(B) N^.(u) = [1], [1, 2], [n] or [n - 1,n] holds for every u e Vf (mj) n Vf (hk).
First, if |N£. (u) | + IN^k (u) | > 4 holds for u e Vf (mj) n Vf (hk), then N£. (u) U N^ (u) is a clique of size greater than 4 in r, a contradiction to the assumption that r does not satisfy the condition (a). Second, we suppose that the condition (B) does not hold. Then we can take a fat vertex u e Vf (mj ) n Vf ( h k ) so that
NS j (u) = [i,i +1]
for i e {2,..., n - 2}. Thus, r has an induced subgraph isomorphic to Si (see Figure 4), a contradiction to the assumption that r does not satisfy the condition (b). Therefore the two conditions (A) and (B) are proved.
h = h' ® hk
[1]
[2, 3]
[4]
Figure 4: An example of the case that r' ~ Pt> and the condition (B) does not hold.
In the case of [hk] = [hi], by the condition (B), the fat vertex u in hk equals
Nfj ([1]), Nfj ([1, 2]), Nfj ([n]) or Nf ([n - 1,n])
for some j = 1 or 2. If u = Nf ([1]) or Nf ([n]) then r is isomorphic to Py for some y G TP. Otherwise, without loss of generality we can assume that
u = Nf([1, 2]).
t1 = t2 = 1 by the condition (A). Hence, r is isomorphic to Py for some y e TP.
Then ti = t'2
We consider the case of [hk] = [h4] or [hr]. If n = 2 then the desired result holds. Thus, we may assume that n > 3. Then
u = Nf. ([i,i + 1]) for every fat vertex u e Vf (hk) and 1 < i < n - 1 (4.5)
since if (4.5) does not hold then h has an induced subgraph isomorphic to either S1 or S2 (see Figure 5), a contradiction. Let u and v are distinct fat vertices of hk. Then one of the following holds:
(i)	u = Nf j ([1]) and v £ Vf (h'), or u = Nf. ([n]) and v £ Vf (h');
(ii)	u = Nf j ([1]),v = Nf j ([n])
by exchanging u and v if necessary. Hence, h = h' ® hk is isomorphic to either Py for some y e TP or Cy for some y e TC.	□
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
567
[1,2]	[3,4]	[5]
Figure 5: An example of the case that r' = Pt>, hk — h4 and u = ([1,2]).
Example 4.12. In Theorem 4.11, there are the two conditions that a slim {[hr]}-line graph has a unique strict H-cover up to equivalence. For each condition, we give an example.
We let G and h denote the slim {[hr]}-line graph and its strict H-cover in Figure 6, respectively. Then, the clique number c of G is equal to 4, and the set K of small circles of G is a maximal clique. Namely, G satisfies the condition (a) in Theorem 4.11. Take a vertex x in K. As shown in Lemma 4.6, K = C (x) holds. Since K = C (x) G cov h, we have
^g(K) = ^G(Ch(x)) = cov h.
As with the proof of Proposition 4.3, we derive the Hoffman graph h by adding fat vertices according to ^g(K).
Figure 6: A slim {[hr]}-line graph whose clique number c is 4 and its strict H-cover corresponding to ^g(K).
Next, we let H and m denote the slim {[hr]}-line graph and its strict H-cover in Figure 7, respectively. Let H' be the subgraph induced by the small circles in H. Then, the clique number c of H is equal to 3, and H' is isomorphic to S1. Namely, H satisfies the condition (b) in Theorem 4.11. Let K be the triangle of H'. Take a vertex x in K. As shown in Lemma 4.7, the vertices in K are adjacent to the same fat vertex of m. In
568	Ars Math. Contemp. 17 (2019) 493-514
particular, K = Cm(x) holds. Since K = Cm(x) G cov m, we have
^h (K) = ^h (Cm(x)) = cov m.
As with the proof of Proposition 4.3, we derive the Hoffman graph h by adding fat vertices according to (K). Similarly, for a slim j[hr]}-line graph in Figure 8, we can construct its strict H-cover.
Figure 7: A slim {[hr]}-line graph containing Si induced by the small circles and its strict H-cover corresponding to ^G(K).
(Hgho-oàAf
Figure 8: A {[h7]}-line graph containing S2 induced by the small circles and its strict H-cover corresponding to (K).
Remark 4.13. Let r be a connected slim j[hr]}-line graph with the clique number at least 2. Let K be a maximal clique of r. We suppose that |K| > 4 when r satisfies the condition (a) in Theorem 4.11, and that K contains the triangle of Si or that of S2 when r satisfies the condition (b). Then, as shown in Lemma 4.6, the strict {[h1], [h4], [hr]}-cover
is cov-1(^r(K)).
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
569
5	The minimal forbidden graphs for the slim {[h 7] }-line graphs
The following theorem is the main result in this paper.
Theorem 5.1. A graph is a minimal forbidden graph for the slim {[hr]}-line graphs if and only if it is one of the following graphs:
(i)	Mi (i = 1, 2,3,4,6, 7,11,12,19) in Figure 9;
(ii)	odd cycles with at least 5 vertices;
(iii)	graphs in Figures 11 and 13.
We explain the reason that the graphs in Figure 9 are minimal forbidden graphs for the slim {hr}-line graphs. They are obtained by enumeration by Magma. The following briefly describes the program.
The MAGMA program is available at [8]. It is also available at https://doi.org/ 10.26493/1855-397 4.1581.b4 7.
Hoffman graphs can construct large new graphs little by little from small graphs by using the concept of sum. With this method, all possible {[hr]}-line graphs with a small number of slim vertices can be obtained by considering all cases where fat vertices can be stuck together. Therefore, we can obtain all slim {[hr]}-line graphs with a small number of vertices. On the other hand, the graphs up to 10 vertices have databases in Magma [2]. Using this, the list F of graphs with at most 10 vertices that are not slim {[hr] }-line graphs is completely revealed. After that, the set of minimal elements of F can be calculated. We will prove Theorem 5.1 separately.
(C1) r has an induced subgraph isomorphic to Si, S2 or the complete graph K4;
(C2) For any maximal clique K containing the largest clique of some induced subgraph isomorphic to S1, S2 or K4, ^r(K) is a partition of V(T).
Proposition 5.2. Let r be a minimal forbidden graph for the slim {[hr]}-line graphs with at least 10 vertices. Then, r does not satisfy the condition (C1) if and only if r is an odd cycle.
Proof. It is easy to verify that every odd cycle with at least 5 vertices is a minimal forbidden graph. Thus, the necessity is proved. Next, we prove the sufficiency. Pick two vertices x and y to determine the diameter of r. Then, r - x and r - y are connected and slim {[hr]}-line graphs. By Theorem 4.11, r — x is isomorphic to either Pt for some t G TP or Ct for some t G TC. We have
|Nr(x)|< 4	(5.1)
since r — y is also isomorphic to either Pt for some t G TP or Ct for some t G TC. By (4.1) and (4.2), which are the definition of TP and TC, we have the length l of t is at least
6	since
i
E ti = ir| — 1 > 9.
i=i
In the rest of this proof, we will consider the decision on whether the vertex is end or non-end in r — x.
570
Ars Math. Contemp. 17 (2019) 493-514
Figure 9: The minimal forbidden graphs for the slim {[hr]}-line graphs, with at most 9 vertices.
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III	571
Step 1: Show that Nr(x) n	is non-empty if z is a non-end vertex in Nr(x).
Suppose that Nr(x) n Nr-x(z) is empty. Then, there exists two distinct vertices u and v of r - x such that u ~ z ~ v and u v. It is a contradiction that Mi ~ (jx, z, u, v})r.
Step 2: Show that |Np(x) n(z)| < 1 for z G Np(x). Suppose |Np(x) nNp_x(z)| > 2, and let zi and z2 be two distinct vertices in Nr(x) n Nr-x(z). We have zi z2 since K4 ~ (jx, z, z1, z2})r if z1 ~ z2. Thus, z is non-end. Let i be the integer such that z G [i]. Then, the following hold:
(i)	if (ti_i, ti, ti+i) = (1,1,2), then M3 ~ (jx} u [i - 1, i, i + 1])r;
(ii)	if (ti-i, ti, ti+i) = (1,2,1), then M2 ~ (jx} u [i - 1, i, i + 1])r;
(iii)	if (ti-i, ti, ti+i) = (2,1,2), then M3 is isomorphic to an induced subgraph in jx} U
[i - 1, i, i + 1].
Then, r is isomorphic to either M2 or M3 by the minimality of r. This is a contradiction to
|V(r)| > 10. Consider the case of (ti-i,ti,ti+i) = (1,1,1). If |Np(x)| = 3 then r ~ Pv or Cf where t' = (ti,...,ti-i, 2,t>+i,... ,t). Otherwise, |Nr(x)| = 4 holds by (5.1), and hence we let jz, zi, z2, z3} = Nr(x). Then, the following hold:
(i)	if z3 G [i - 2, i + 2] then M3 ~ (jx} U Nr(x))r;
(ii)	if z3 G [i - 2, i + 2] then Mi ~ (jx, zi, z2, z3})r (see Figure 10). These are contradictions to |V(r)| > 10.
Figure 10: Examples of the case that (ti_i, ti, ti+i) — (1,1,1) and |Np (x) | — 4 in Step 2.
Step 3: Show that the vertices in Nr(x) are end. Suppose that a vertex z is non-end in Nr(x). By Step 1 and 2, |Nr(x) n Nr_x(z)| — 1 holds. Thus, we can take a vertex z1 so that
{zi} — Nr(x) n Nr_x(z).
There are i and j such that z G [i] and z1 G [j]. Let I — [i, j, i ± 1, j ± 1]. It follows that Nr(x) n I — {z, z1} by Step 2. If z1 is non-end, then some induced subgraph of r is isomorphic to M1 if i — j, S1 otherwise, a contradiction. Otherwise, we may assume that i — 2 and j — 1 without loss of generality. Then, the following hold:
(i) if (t1, t2) — (2,1), then M1 is isomorphic to some induced subgraph of r;
(ii) if (t1, t2) — (1,2), then M3 is isomorphic to some induced subgraph of r;
572
Ars Math. Contemp. 17 (2019) 493-514
(iii)	if (ii, t2) = (1,1) and |Nr(x)| > 3, then r has an induced subgraph isomorphic to
Si or S2;
(iv)	if (ti,t2) = (1,1) and |Nr(x)| = 2, then r ~ P(t1 + i,t2,...,t,). The result follows. Moreover, r - x is isomorphic to Pt.
Step 4: For i = 1 or l, if Nr(x) n [i] = 0 then Nr(x) n [i] = [i] since Nr(x) n [i] = [i] implies that r has an induced subgraph isomorphic to Si by Step 3.
Step 5: If Nr(x) = [1] then r ~ P(i,t1,...,tt) is an j[hr]}-line graph, a contradiction. Hence, r ~ C(i,il,...,ii). If l is odd then C(i,tl,...,tl) is an j[hr]}-line graph, a contradiction. Thus, r is an odd cycle.	□
Proposition 5.3. Let r be a minimal forbidden graph for the slim {[h7]}-line graphs, with at least 10 vertices and the condition (C1). Then, r is isomorphic to one of the graphs in Figure 11 if and only if r does not satisfy the condition (C2).
Axo xi x2l-i x2l / \ >-•—-•-d--*-•
. A ■■ ■ A ..
Figure 11: Minimal forbidden graphs for the slim j[hr]}-line graphs, with at least 10 vertices and the condition (C1), without (C2).
Proof. It is easy to verify that ^r(K) is not a partition, where r is one of the graphs of Figure 11, and K is the rightmost clique of size at least 3.
Next, we prove the necessity. By the condition (C1), r has an induced subgraph isomorphic to Si, S2 or K4. Hence, we can take a maximal clique K containing the largest clique of some induced subgraph S isomorphic to S1, S2 or K4. Since the condition (C2) is not satisfied, we may suppose that ^r(K) is not a partition of V(r). If |K| > 3 then we replace S by (K')r, where K' is a set of 4 vertices in K. Let l = |_(dmax - 1)/2J and V' = {x e V(r) | 3k(x) < 2l}.
Step 1: There is a vertex g not in V(S) U K with 3k(g) = dmax. Then, {C e ^r(K) | 3k(c) < 2l for any c e C} = {C e (K) | 3k(c) < 2l for any c e C} is a clique partition of V' since r - g is a slim {[h7]}-line graph satisfying the condition (a) or (b) in
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
573
Theorem 4.11. Therefore, (K) is not a partition if and only if there exists vertices x, y, p and q such that dK (x) = dK (y) = 2/ +1,
and
q € ((N(x) U{x}) n (N(y) U {y})) - V'
p € ((N(x) U {x}) - (N(y) U {y})) - V'.
If z € V(r) - ({x, y,p, q} U S) with Ok(z) > 2/ + 1, then r - z is an {[hr]}-line graph and p — y by Remark 4.13. This is a contradiction to p — y. It follows that
{u € V(r) | dK(u) > 2/ + 1} - V(S) = {x, y,p, q}.	(5.2)
Step 2: Assume that / = 0. In the case of |K| > 4 (i.e., S — K4),
{K - {k}, {x, y,p, q}} C ^r-fc(K - {k})
is a clique partition for some k € K by Remark 4.13 and (5.2), i.e., |K| > 6. This is a contradiction to p — y. In the case of |K| = 3 (i.e., S — S1 or S2), we obtain |V(r)| < 9 and a contradiction. Hence, / is a positive integer.
Step 3: Show that x — y. In addition, it holds that x = p and x = q. Suppose that x and y are not adjacent. Then, p = x and q € {x, y} by Remark 4.13. If x and y are adjacent to a vertex r with dK (r) = 2/, then r has an induced subgraph isomorphic to K1j3, a contradiction. When dK (q) = 2/ + 1, there is a neighbor q' of q with dK (q') = 2/ such that q' € N(x) n N(y). Without loss of generality we assume that q' and y are not adjacent. Then, the induced subgraph r' obtained by deleting the neighbors of y expect q has a clique partition (K) which contains a set {x, y, q}. This is a contradiction, and dK (q) = 2/ + 2 follows. Then, r has an induced subgraph isomorphic to an odd cycle with at least 5 vertices. This is a contradiction since (K) is a clique partition in Or-q.
Step 4: Let P denote a path (x0,..., x2i+1) such that x0 € K and x = x2I+1. If S — K4, then replace S by (K'}r, where K' is a set of 4 vertices in K containing x0 and a vertex not adjacent to x1. The graph r' by deleting vertices other than V(P) U V(S) U {x, y,p} is a slim {[h7]}-line graph with a clique partition (K). Thus, it holds that V(r) =
V(P) U V(S) U {x, y,p} and y - x2i.
Step 5: If dK(p) = 2/ + 1, then p — x2l. Thus, ({y,p, x2l, x2l-1}}r — K13 holds, a contradiction. Thus, dK (p) =2/ + 2.
Step 6: In the case of |K| > 4 (i.e., S — K4), deg(x1) < 3 since r - p is an {[hr]}-line graph. Obtain the second and third graphs in Figure 11.
Step 7: In the case of |K| = 3 (i.e., S — S1 or S2), if x1 € S then |N(x1) n K| = 1 since M1 and M3 are minimal forbidden graphs for the slim {[hr]}-line graphs. Then, we can replace S by the induced subgraph by K U {x1, w}, where w is a vertex of S not adjacent to x0. Hence, x1 € S holds. We can draw r as Figure 12. The edge e exists if and only if the edge e' does in Figure 12. If the edges e and e' exist, then r - x0 is not an {[hr]}-line graph. Otherwise, we obtain the first graphs in Figure 11.	□
Let r be a connected graph, and let K and D be nonempty subsets of V(r). D is said to be deletable for K if K - D = 0, r - D is connected, and (K - D) = {C - D |
574
Ars Math. Contemp. 17 (2019) 493-514
xo xi
x
p
Figure 12: In the proof of Proposition 5.3.
C € ^r(K )}-{0}. In addition, a vertex v is said to be deletable for K if {v} is deletable for K.
Lemma 5.4. Let r be a connected graph, and let K and D be nonempty subsets of V(r). If ^r(K) is a partition of V (r) and dK,r |r-D = dK-D,r-D, then D is deletable for K.
Proof. Write d = dK,r for short. Then, it holds that by dK,r |r-D = dK-D,r-D,
^r-D(K - D) -{K - D}
= {{y € ({x} U N(x)) - D | d(y) > d(x)} | x € V(r - D), d(x) € 2N + 1},
{C - D | C € ^r(K)} - {K - D}
= {{y € ({x} U N(x)) - D | d(y) > d(x)} | x € V(r), d(x) € 2N + 1}.
Let x € D with odd d(x), and take Cx € (K) containing x. Assuming that Cx -D = 0, there exists z € C such that d(z) = d(x) by the assumptions. It holds that
Cx - D = {y € ({x} U N(x)) - D | d(y) > d(x)}
Lemma 5.5. Let r be a minimal forbidden graph for the slim {[h7] }-line graphs, with the condition (C1) and(C2). Let S be an induced subgraph isomorphic to Si, S2 or K4. Let K be a maximal clique of r contains the largest clique of S. Then, the following hold:
(i)	^r(K) is a clique partition;
(ii)	if u is a non good vertex for ^r(K), and v € V(S) U K is a deletable vertex for K, then v € n3(u) and v is non good for (K), where nk (■) is defined for ^r(K) and a non negative integer k.
Proof. By the condition (C2), ^r(K) is a partition of V(r). Moreover, it is a clique partition of V(r) by Lemma 4.5 since r has no induced subgraph isomorphic to M1 ~ K1,3. Next, suppose that the vertex v is not in n3(u). Then,
{C n n3(u) | C € ^r(K)} = {C n n3(u) - {v} | C € (K)}
= {C n n3(u) | C € ^r-v(K)}
holds. Thus, the vertex u is good for ^r-v (K) if and only if it is good for ^r-v (K) in r - v by Lemma 4.4. On other hand, v € V(S) U K and r - v is connected. Hence, ^r-v(K) € Or-v, that is, every vertex of r - v is good for ^r(K) by Remark 4.13 since r is a minimal forbidden graph for the slim {[hr]}-line graphs. Therefore, u is good for ^r-v (K) and (K). This is a contradiction that u is non good for ^r(K).	□
and
{y G ({z} u N (z)) - D | d (y) > d(z)} G (K - D). □
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
575
Proposition 5.6. Let r be a minimal forbidden graph for the slim {[hr ]}-line graphs, with at least 10 vertices and the condition (C1). Then, r is one of the graphs in Figure 13 if and only if r satisfies the condition (C2).
" \** the number of vertices is odd ^	' ------®
KT------13
Figure 13: The minimal forbidden graphs for the slim {[hr]}-line graphs, with at least 10 vertices and the conditions (C1) and (C2).
Proof. The sufficiency obviously holds. Prove the necessity. Fix an induced subgraph S isomorphic to S1, S2 or K4, and let K be a maximal clique containing the largest clique of S. By Lemma 5.5 (i), ^r(K) is a clique partition. Then, nk ( ) is defined for ^r(K) and a non negative integer k.
If r has an induced subgraph isomorphic to K4, then replace S by it. Let l = |_(dmax -1)/2j. By the definition of ^r(K), we can pick the subset
{{y G N(x) U {x} | 3k(y) > Ok(x)} | x G V(r), 3k(x) = 2l +1}
of ^r(K). We denote by {Cj}"=1 the subset. Note that Cj are pairwise distinct. If l = 0 then let D1 = K and m =1. Otherwise we pick the subset
{{y G N(x) U {x} | 3k(y) > 3k(x)} | x G V(r), 3k(x) = 2l - 1}
of ^r(K). We denote by {A}"= 1 the subset. Note that A are pairwise distinct. Without loss of generality, we can take an integer m such that A - V(S) is empty if and only if i > m.
In the case of dmax = 2l + 1, we show that r is isomorphic to one of the graphs in Figure 13.
576
Ars Math. Contemp. 17 (2019) 493-514
Step 1: Show that l = 0. Suppose that l = 0 to prove by contradiction. Set B = V(r) — (V(S) U K). Then, every vertex in B is deletable by Lemma 5.4. Moreover, the deletable vertex is non good for ^r(K) by applying Lemma 5.5 (ii) to a non good vertex for (K) and the deletable vertex. We obtain a contradiction by checking the following:
(i)	|B| < 3;
(ii)	if 7 < |V(r) — K|, then 5 < |V(r) — K| — 2 < |B|;
(iii)	if 4 < |V(r) — K| < 6, then S ~ K4 and 4 < |B|;
(iv)	if |V(r) — K| < 3, then r is an {[hr]}-line graph.
Assume that |B| > 4. If we find a vertex k e K with |n(k) | > 3, then we can take a vertex b e B such that |n(k) — {b}| > 3. This is a contradiction since the vertex b is deletable and ^r-b(K) e Or-b by Remark 4.13. Thus,
|n(k)|< 2	(5.3)
holds for every k e K. Fix a vertex b e B. Then, |n(b)| > 3 holds by (5.3) and applying Lemma 5.5 (ii) to the non good vertex b and each vertex in B — {b}. We obtain a contradiction as well and |B| < 3. Next, In the case of |V(r) — K| < 3, we have |B| < 3, |K| > 7 and hence S ~ K4. If 2 < |B| < 3, then |n(b)| < 2 for every vertex b e B. Hence, we can pick a vertex k in
K — J n(b).
beB
It is clear that k is deletable and (K — {k}) e Or-k. Thus every vertex of r is good for (K), a contradiction to r being a non {[hr]}-line graph.
Step 2: Every vertex x with dK(x) = dmax is not in V(S) U K and deletable by l > 1 and Lemma 5.4. Moreover, such a vertex x is non good for ^r(K) by applying Lemma 5.5 (ii) to a non good vertex for ^r(K) and the deletable vertex x. Fix a vertex u with dK (u) = dmax. By applying Lemma 5.5 (ii) to u and each vertex x with dK (x) = dmax, we have
{x e V(r) | dK(x)= dmaxK n2(u)
since r has no induced subgraph isomorphic to Mi ~ Kij3. For a vertex x with dK (x) = dmax — 1 = 2l, it holds that x e n3(u) since if n(x) = 0 then x is deletable by Lemma 5.4 and x e n3(u) holds by applying Lemma 5.5 (ii) to the vertices u and x. Thus,
n3(u) = {x e V(r) | Bk(x) > 2l}.	(5.4)
Furthermore, Dj contains a vertex v with dK (vj) = dmax — 1 for every 1 < i < m, since every deletable vertex not in V(S) U K is contained in n3(u) by Lemma 5.5 (ii).
Step 3: Show that n = m =1. If n > 2 then r has an induced subgraph isomorphic to M1 by (5.4), a contradiction. Thus, n =1. Suppose that m > 2 to prove by contradiction. Without loss of generality, we can assume that vi ^ u ^ V2 by (5.4). In the case of m > 3,
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
577
the vertex v3 is deletable clearly, and the vertex u is non good for ^r-V3 (K) in r - v3. This is a contradiction to ^r-d3 (K) G Or-d3 by Remark 4.13.
In the case of m = 2, we have C1 = {u} since if we find an vertex u' in C1, then the vertex u' is deletable by Lemma 5.4 and u is non good for	(K) in r - u', a
contradiction to (K) G Or_«'. Fix a vertex v' G Dj with dK (v') = 21 -1 for i = 1 and 2, respectively. Then, the set
Di U D2 - (V(S) U{vi,v2,vi,v2})
is deletable and u is good. Hence, the set is empty. If v1 and v2 are not adjacent in r, then r has an induced subgraph isomorphic to an odd cycle with at least 5 vertices since u is deletable and ^r(K) - {C1} = ^r_„(K) g Or-u. This is a contradiction to the minimality of r. Hence, v1 and v2 are adjacent in r. First, consider the case of 1 > 2. Let d be the vertex adjacent to v2 with dK (d) = 21 - 2. Note that d is not in S. Then, r - d
is not an {[hr]}-line graph since ^r-d(K) G Or—d (cf. Figure 14). Second, consider the case of l = 1. Suppose that S ~ K4. Note that n' = m = 2 holds. If |K| > 5, then we can take a deletable vertex k in K. By Remark 4.13, ^r—fc(K - {k}) G Or—k holds since K - {k} is a maximal clique with at least 4 vertices. However, u is non good for k(K - {k}), a contradiction to the minimality of r. We have |V(r)| = |K| + |D11 + |D21 + |C11 = 4 + 2 + 2 +1 = 9, a contradiction to |V(r) | > 10. Thus, r has no induced subgraph isomorphic to K4. Suppose that S ~ S1 or S2. We define the vertices w of S as Figure 15. Note that the vertex v' is not in V(S) for i = 1,2 since | V(r) | > 10. If both v1 and v2 are adjacent only to w1, then r has an induced subgraph isomorphic to M1, a contradiction. Hence, it is not so. Without loss of generality, we can assume that v2 and w2 are adjacent. Since r has no induced subgraph isomorphic to K4, v'2 is not adjacent to some vertex w G {w1, w3}. The vertices v'2 and w5 are adjacent since (v2, w, w2, w5)r is not isomorphic to M1. Furthermore, v2 is also adjacent to w5 since ^r(K) is a clique partition. Hence, v2 is deletable for K, a contradiction to We have n = m =1.
Step 4: Let p = |C11 and q = |{x G V(r) | Ok(x) = 2l}|. The induced subgraph (C1 U D1)r is an {[h7]}-line graph by the minimality of r. Hence, ^(CiuDi)r(D1) =
578
Ars Math. Contemp. 17 (2019) 493-514
{Ci, Di j holds by |Di| > 4 and Remark 4.13. This is a contradiction since non good vertices for ^r(K) in Ci U Di are also non good for ^(ClUDl)r (Di). Thus, q < 2. When q = 1, p = 3 holds and we obtain the second and third graph in Figure 13 in the same way as the Step 4 in the proof of Proposition 5.3. Consider the case of q = 2. If p =1 then r is an {[h7]j-line graph. When p = 2, we obtain the first and second graph in Figure 13 since r has no induced subgraph isomorphic to M3. If p > 3 then we can assume that n(u) = {x G V(r) | dK(x) = 21} by (5.4). Then, r - w is not an {[hr] j-line graph for some w G Ci — {v j, a contradiction.
Suppose that dmax = 21 + 2. We have 1 > 0 and every vertex u with dK (u) = 21 + 2 is deletable for K. By Lemma 5.5 (ii), the vertex u is non good for ^r(K). Moreover, every vertex v with dK (v) < 21 + 1 is good for ^r(K) since (n3(v))r is the induced subgraph of r — u, where dK (u) =21 + 2. Hence, a vertex u is good if and only if dK (u) < 21 + 1. We have n =1 since a vertex v with dK(v) = 21 + 2 is non good. Let v be a vertex with dK(v) = 21 + 1. If v is not a vertex of S, then we have a contradiction to Lemma 5.5 (ii) that v is deletable for K. Hence, v is a vertex of S. Thus, S ~ Si, 1 = 0 and n = 2. Then, | V(r) | < 9 since |K| = 3, |Ci | < 3 and |C2| < 3, a contradiction.	□
Proof of Theorem 5.1. The minimal forbidden graphs with at most 9 vertices are revealed in Figure 9. This theorem follows by Proposition 5.2, 5.3 and 5.6.	□
References
[1]	L. W. Beineke, Characterizations of derived graphs, J. Comb. Theory 9 (1970), 129-135, doi: 10.1016/s0021-9800(70)80019-9.
[2]	W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24 (1997), 235-265, doi:10.1006/jsco.1996.0125.
[3]	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, doi:10.1016/0021-8693(76)90162-9.
S. Kubota et al.: On graphs with the smallest eigenvalue at least — 1 — \/2, part III
579
[4]	M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), 51-229, doi:10.4007/annals.2006.164.51.
[5]	M. C. Golumbic, Trivially perfect graphs, Discrete Math. 24 (1978), 105-107, doi:10.1016/ 0012-365x(78)90178-4.
[6]	A.J. Hoffman, On graphs whose least eigenvalue exceeds — 1 — \[2, Linear Algebra Appl. 16 (1977), 153-165, doi:10.1016/0024-3795(77)90027-1.
[7]	H. J. Jang, J. Koolen, A. Munemasa and T. Taniguchi, On fat Hoffman graphs with smallest eigenvalue at least —3, Ars Math. Contemp. 7 (2014), 105-121, doi:10.26493/1855-3974.262. a9d.
[8]	S. Kubota, On (h7}-line graphs, https://sites.google.com/view/s-kubota/ home/magma-programs/on-h7-line-graphs, accessed on April 8, 2019.
[9]	D. P. Sumner, 1-factors and antifactor sets, J. London Math. Soc. 13 (1976), 351-359, doi: 10.1112/jlms/s2-13.2.351.
[10]	T. Taniguchi, On graphs with the smallest eigenvalue at least —1 — -^/2, part I, Ars Math. Contemp. 1 (2008), 81-98, doi:10.26493/1855-3974.35.fe9.
[11]	T. Taniguchi, On graphs with the smallest eigenvalue at least —1 — -^/2, part II, Ars Math. Contemp. 5 (2012), 239-254, doi:10.26493/1855-3974.182.139.
[12]	R. Woo and A. Neumaier, On graphs whose smallest eigenvalue is at least —1 — \[2, Linear Algebra Appl. 226/228 (1995), 577-591, doi:10.1016/0024-3795(95)00245-m.