ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 7 (2014) 247-262 Fat Hoffman graphs with smallest eigenvalue at least — 1 — t Akihiro Munemasa Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan Yoshio Sano Division of Information Engineering, Faculty of Engineering, Information and Systems University ofTsukuba, Ibaraki 305-8573, Japan Tetsuji Taniguchi Matsue College of Technology, Matsue 690-8518, Japan Received 30 November 2011, accepted 14 March 2012, published online 30 April 2013 In this paper, we show that all fat Hoffman graphs with smallest eigenvalue at least -1 - t, where t is the golden ratio, can be described by a finite set of fat (-1 - t)-irreducible Hoffman graphs. In the terminology of Woo and Neumaier, we mean that every fat Hoffman graph with smallest eigenvalue at least -1 - t is an H-line graph, where H is the set of isomorphism classes of maximal fat (-1 - t)-irreducible Hoffman graphs. It turns out that there are 37 fat (-1 - t)-irreducible Hoffman graphs, up to isomorphism. Keywords: Hoffman graph, line graph, graph eigenvalue, special graph. Math. Subj. Class.: 05C50, 05C75 1 Introduction P. J. Cameron, J. M. Goethals, J. J. Seidel, and E. E. Shult [1] characterized graphs whose adjacency matrices have smallest eigenvalue at least -2 by using root systems. Their results revealed that graphs with smallest eigenvalue at least -2 are generalized line graphs, except a finite number of graphs represented by the root system E8. Another characterization for generalized line graphs were given by D. Cvetkovic, M. Doob, and S. Simic [3] E-mail addresses: munemasa@math.is.tohoku.ac.jp (Akihiro Munemasa), sano@cs.tsukuba.ac.jp (Yoshio Sano), tetsuzit@matsue-ct.ac.jp (Tetsuji Taniguchi) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ Abstract 248 Ars Math. Contemp. 7 (2014) 201-213 by determinig minimal forbidden subgraphs (see also [4]). Note that graphs with smallest eigenvalue greater than -2 were studied by A. J. Hoffman [5]. Hoffman [6] also studied graphs whose adjacency matrices have smallest eigenvalue at least -1 - a/2 by using a technique of adding cliques to graphs. R. Woo and A. Neumaier [12] formulated Hoffman's idea by introducing the notion of Hoffman graphs. A Hoffman graph is a simple graph with a distinguished independent set of vertices, called fat vertices, which can be considered as cliques of size infinity in a sense (see Definition 2.1, and also [8, Corollary 2.15]). To deal with graphs with bounded smallest eigenvalue, Woo and Neumaier introduced a generalization of line graphs by considering decompositions of Hoffman graphs. They gave a characterization of graphs with smallest eigenvalue at least -1 - a/2 in terms of Hoffman graphs by classifying fat indecomposable Hoffman graphs with smallest eigenvalue at least -1 - a/2. This led them to prove a theorem which states that every graph with smallest eigenvalue at least -1 - a/2 and sufficiently large minimum degree is a subgraph of a Hoffman graph admitting a decomposition into subgraphs iso-morphic to only four Hoffman graphs. In the terminology of [12], this means that every graph with smallest eigenvalue at least -1 - a/2 and sufficiently large minimum degree is an H-line graph, where H is the set of four isomorphism classes of Hoffman graphs. For further studies on graphs with smallest eigenvalue at least -1 - a/2, see the papers by T. Taniguchi [10, 11] and by H. Yu [13]. Recently, H. J. Jang, J. Koolen, A. Munemasa, and T. Taniguchi [8] made the first step to classify the fat indecomposable Hoffman graphs with smallest eigenvalue -3. However, it seems that there are so many such Hoffman graphs. A key to solve this problem is the notion of special graphs introduced by Woo and Neumaier. A special graph is an edge-signed graph defined for each Hoffman graph. Although non-isomorphic Hoffman graphs may have isomorphic special graphs, it is not difficult to recover all the Hoffman graphs with a given special graph in some cases. In this paper, we introduce irreducibility of Hoffman graphs and classify fat (-1 - t)-irreducible Hoffman graphs, where t := 1+2/^ is the golden ratio. This is a somewhat more restricted class of Hoffman graphs than those considered in [8], and there are only 37 such Hoffman graphs. As a consequence, every fat Hoffman graph with smallest eigenvalue at least -1 - t is a subgraph of a Hoffman graph admitting a decomposition into subgraphs isomorphic to only 18 Hoffman graphs. In the terminology of [12], this means that every fat Hoffman graph with smallest eigenvalue at least -1 - t is an H-line graph, where H is the set of 18 isomorphism classes of maximal fat (-1 - t)-irreducible Hoffman graphs. 2 Preliminaries 2.1 Hoffman graphs and eigenvalues Definition 2.1. A Hoffman graph H is a pair (H, of a graph H and a vertex labeling ^ : V(H) ^ {slim, fat} satisfying the following conditions: (i) every vertex with label fat is adjacent to at least one vertex with label slim; (ii) the vertices with label fat are pairwise non-adjacent. Let V(H) := V(H), Vs(H) := M-1(slim), Vf (H) := M-1(fat), and E(H) := E(H). We call a vertex in V s(H) a slim vertex, and a vertex in Vf (H) a fat vertex of H. We represent a Hoffman graph H also by the triple (Vs (H), Vf (H), E(H)). For a vertex x of a Hoffman graph H, we define Nf (x) (resp. N^ (x)) to be the set of fat (resp. slim) neighbors of x in H. The set of all neighbors of x is denoted by N55 (x), that A. Munemasa et al.: Fat Hoffman graphs with smallest eigenvalue at least — 1 — t 249 is, Nh(x) := Nf (x) U Nft (x). A Hoffman graph H is said to be fat if every slim vertex of H has a fat neighbor. A Hoffman graph is said to be slim if it has no fat vertex. Two Hoffman graphs H = (H, and H' = (H', are said to be isomorphic if there exists an isomorphism from H to H' which preserves the labeling. A Hoffman graph H' = (H', is called an induced Hoffman subgraph (or simply a subgraph) of another Hoffman graph H = (H, if H' is an induced subgraph of H and ^(x) = ^'(x) holds for any vertex x of H'. The subgraph of a Hoffman graph H induced by Vs(H) is called the slim subgraph of H. Definition 2.2. For a Hoffman graph H, let A be its adjacency matrix, C ^ A = ^CT O in a labeling in which the fat vertices come last. The eigenvalues of H are the eigenvalues of the real symmetric matrix B(H) := As - CCT. We denote by Amin(H) the smallest eigenvalue of B(H). Remark 2.3. An ordinary graph H without vertex labeling can be regarded as a slim Hoffman graph H. Then the matrix B(H) coincides with the ordinary adjacency matrix of the graph H. Thus the eigenvalues of H as a slim Hoffman graph are the same as the eigenvalues of H as an ordinary graph in the usual sense. Example 2.4. Let Hi, Hii, and Hiii be the Hoffman graphs defined by V s(Hi) = {vi}, Vf (Hi) = {fi}, E (Hi) = {{vi,fi}}, Vs(Hii) = {vi}, Vf (Hii) = {fi, /2}, E(Hii) = {{vi, fi}, {vi, M}, Vs(Hiii) = {vi, v2}, Vf (Hiii) = {/i}, E(Hiii) = {{vi, fi}, {v2, fi}} (see Figure 1). Note that Amin(Hi) = -1 and Amin(Hii) = Amin(Hiii) = -2. A V Hi Hii Hiii Figure 1: The Hoffman graphs HI, Hn, and HIII Lemma 2.5 ([12, Lemma 3.4]). The diagonal entry B(H)xx of the matrix B(H) is equal to — |Nf (x)|, and the off-diagonal entry B(H)xy is equal to Axy — |Nf (x) n Nf (y)|. Lemma 2.6 ([12, Corollary 3.3]). If G is an induced Hoffman subgraph of a Hoffman graph H, then Amin(©) > Amin(H) holds. In particular, if r is the slim subgraph of H, then Amin(r) > Amin(H). 250 Ars Math. Contemp. 7 (2014) 201-213 2.2 Decompositions of Hoffman graphs Definition 2.7. A decomposition of a Hoffman graph H is a family {H®}^ of Hoffman subgraphs of H satisfying the following conditions: (i) V(H) = UI=i V(H®); (ii) Vs (H®) n Vs(Hj) = 0 if i = j; (iii) if x G Vs (H®), y G Vf (H), and {x,y} g E(H),then y G V(H®); (iv) if x G Vs(H®), y G Vs(Hj), and i = j, then |Nf (x) n Nf (y)| < 1, and |Nf (x) n Nf (y) | = 1 if and only if {x, y} G E(H). If a Hoffman graph H has a decomposition {Hi}n=1, then we write H = 1+1"=1 H®. Example 2.8. The (slim) complete graph Kn is precisely the slim subgraph of the Hoffman graph H = 1+)¡=1 H® where each H® is isomorphic to Hi, sharing the unique fat vertex. Ordinary line graphs are precisely the slim subgraphs of Hoffman graphs H = 1+)¡=1 H®, where each H® is isomorphic to HII. The (slim) cocktail party graph CP(n) = Knx2 is precisely the slim subgraph of the Hoffman graph H = 1+1 "=1 H® where each H® is isomorphic to Hm, sharing the unique fat vertex. Generalized line graphs are precisely the slim subgraphs of Hoffman graphs H = (±11= H®, where each H® is isomorphic to Hn or HIII (see [12]). Definition 2.9. A Hoffman graph H is said to be decomposable if H has a decomposition {H®}n=1 with n > 2. We say H is indecomposable if H is not decomposable. Example 2.10. A disconnected Hoffman graph is decomposable. Definition 2.11. Let a be a negative real number and let H be a Hoffman graph with Amin(H) > a. The Hoffman graph H is said to be a-reducible if there exists a Hoffman graph H' containing H as an induced Hoffman subgraph such that there is a decomposition {H®}2=1 of H' with Amin(H®) > a and Vs(H®) n Vs(H) = 0 (i = 1,2). We say H is a-irreducible if Amin(H) > a and H is not a-reducible. A Hoffman graph H is said to be reducible if H is Amin(H)-reducible. We say H is irreducible if H is not reducible. Lemma 2.12 ([8, Lemma 2.12]). If a Hoffman graph H has a decomposition {H®}"=1, then Amin(H) = min{Amin(H®) | 1 < i < n}. In particular, an irreducible Hoffman graph is indecomposable. Example 2.13. For a non-negative integer t, let K1t be the connected Hoffman graph having exactly one slim vertex and t fat vertices, i.e., Km = (Vs(KM), Vf (Km), E(K1,t)) = ({v}, {/1,..., ft}, {{v, f®} | i = 1,... t}). Then K1jt is irreducible and Amin(K1jt) = -t. Example 2.14. By Example 2.13, the Hoffman graphs Hi (= Ki,i) and Hii (= Ki,2) are irreducible. The Hoffman graph Hm is also irreducible. A. Munemasa et al.: Fat Hoffman graphs with smallest eigenvalue at least — 1 — t 251 Example 2.15. Let Hiv be the Hoffman graph defined by Vs(Hiv) = {vi, v2}, Vf (Hiv) = {/i, /2} and E(Hiv) = {{vi,«2}, {vi,/i}, {v2,/2}}. The Hoffman graph HIV is indecomposable but reducible. Indeed, it is clear that HIV is indecomposable. Let H' be the Hoffman graph obtained from HIV by adding a new fat vertex f3 and two edges {vi, /3} and {v2, /3}. The Hoffman graph H' is the sum of two copies of HII, where the newly added fat vertex is shared by both copies, that is, H' is decomposable. Furthermore, Amin(Hn) = Amin(HIV) = -2. Hence HIV is reducible. Proposition 2.16. Let G be a slim graph with at least two vertices. If G has maximum degree k, then G is (-k)-reducible. Proof. Let G be a slim graph with maximum degree k. We define a Hoffman graph H by adding a fat vertex for each edge e of G and joining it to the two end vertices of e. Note that G is the slim subgraph of H. For each slim vertex x G Vs(H), let Hx be the Hoffman subgraph of H induced by {x} U Nf (x). Then Hx is isomorphic to the Hoffman graph K^degcO) defined in Example 2.13, and we can check that H = 1+1xeVs(^) Hx. Since the maximum degree of G is k, Amin(Hx) = - degG(x) > -k. Thus G is (-^-reducible. □ Definition 2.17. Let H be a family of isomorphism classes of Hoffman graphs. An H-line graph is an induced Hoffman subgraph of a Hoffman graph which has a decomposition {Hi}n=i such that the isomorphism class of H® belongs to H for all i = 1,..., n. 2.3 The special graphs of Hoffman graphs Definition 2.18. An edge-signed graph S is a pair (S, sgn) of a graph S and a map sgn : E(S) ^ {+, -}. Let V(S) := V(S), E+(S) := sgn-i(+), and E-(S) := sgn-i(-). Each element in E +(S) (resp. E-(S)) is called a (+)-edge (resp. a (-)-edge) of S. We represent an edge-signed graph S also by the triple (V(S), E+(S), E-(S)). An edge-signed graph S' = (S', sgn') is called an induced edge-signed subgraph of an edge-signed graph S = (S, sgn) if S' is an induced subgraph of S and sgn(e) = sgn'(e) holds for any edge e of S'. Two edge-signed graphs S and S' are said to be isomorphic if there exists a bijection ^ : V(S) ^ V(S') such that {u,v} G E+(S) if and only if {^(w),^(v)} G E+(S') and that {u,v} G E-(S) if and only if {^(w),^(v)} G E-(S'). An edge-sined graph S is said to be connected (resp. disconnected) if the graph (V(S), E +(S) U E-(S)) is connected (resp. disconnected). Example 2.19. A connected edge-signed graph with at most two vertices is isomorphic to one of the edge-signed graphs Si,i, S2,i, and S2,2, where V (Si,i) = {vi}, E+(Si,i) = 0, E-(Si,i) = 0, V (S2,i) = {vi,V2}, E+(S2,i) = {{vi,v2}}, E-(S2,i) = 0, V (S2,2) = {vi,V2}, E+(S2,2) = 0, E-(S2,2) = {{vi, V2}}. (see Figure 2 in which we draw an edge-signed graph by depicting (+)-edges as full lines and (-)-edges as dashed lines). 252 Ars Math. Contemp. 7 (2014) 201-213 Sl,l S2,1 S2,2 Figure 2: The connected edge-signed graphs with at most two vertices Definition 2.20. The special graph of a Hoffman graph H is the edge-signed graph S(H) :=(V(S(H)),E+(S(H)),E-(S(H))) where V(S(H)) := Vs(H) and E+(S(H)) := {{u, v} | u, v e Vs(H), u = v, {u, v} e E(H), (u) n (v) = 0}, E-(S(H)) := {{u, v} | u, v e Vs(H),u = v, {u, v} e E(H),Nf (u) n (v) = 0}. Lemma 2.21 ([8, Lemma 3.4]). A Hoffman graph H is indecomposable if and only if its special graph S(H) is connected. Definition 2.22. For an edge-signed graph S, we define its signed adjacency matrix M(S) by (l if {u,v}e E+(S), (M(S))uv = J -1 if {u,v} e E-(S), [ 0 otherwise. We denote by Amin(S) the smallest eigenvalue of M (S). We remark that P. J. Cameron, J. J. Seidel, and S. V. Tsaranov studied the eigenvalues of edge-signed graphs in [2]. Lemma 2.23. If S' is an induced edge-signed subgraph of an edge-signed graph S, then Amin(S') > Amin (S). Proof. Since M(S') is a principal submatrix of M(S), the lemma holds. □ Lemma 2.24. Let H be a Hoffman graph in which any two distinct slim vertices have at most one common fat neighbor. Then M (S (H)) = B(H) + D(H), where D(H) is the diagonal matrix defined by D(H)xx := |Nf (x) | for x e Vs (H). Proof. This follows immediately from the definitions and Lemma 2.5. □ Lemma 2.25. If H is a fat Hoffman graph with smallest eigenvalue greater than -3, then Amin(S(H)) > Amin(H) + 1. Proof. If some two distinct slim vertices of H have two common fat neighbors, then H contains an induced subgraph with smallest eigenvalue at most -3. This contradicts the assumption by Lemma 2.6. Thus the hypothesis of Lemma 2.24 is satisfied. Since H is fat, the smallest eigenvalue of M(S(H)) = B(H) + D(H) is at least Amin(H) + 1 by [7, Corollary 4.3.3], proving the desired inequality. □ A. Munemasa et al.: Fat Hoffman graphs with smallest eigenvalue at least — 1 — t 253 3 Main Results 3.1 The edge-signed graphs with smallest eigenvalue at least —t Definition 3.1. Let p, q, and r be non-negative integers with p + q < r. Let Vp, Vq, and Vr be mutually disjoint sets such that |Vj| = i where i e {p, q, r}. Let Up and Uq be subsets of Vr satisfying |Up| = p, |Uq| = q, and Up n Uq = 0. Let Qp,q,r be the edge-signed graph defined by V( Qp,q,r ) := Vp U Vq U Vr, E+(Qp,q,r) := {{u,v}| u e Up,v e Vp}U{{v,v'}| v,v' e Vr,V = v'}, E-(Qp,q,r) := {{u,v}| u e Uq,v e Vq} (see Figure 3 for an illustration). Figure 3: £3,2,6 Lemma 3.2. For any non-negative integersp, q, and r with p+q < r, Am;n(Qp,q,r) > —t. Proof. Let M (Qr,r,2r ) Multiplying I 0 xI 0 0 I 0 - xI 0 0 I 0 0 0 0 I 0 0 I 0 0 0 0 -I 1 0 J -1 J 0 -I J J-I 254 Ars Math. Contemp. 7 (2014) 201-213 from the left to xI - M(Qr,r,2r), we find |x/ - M (Qr,r,2r )| = (-1) r (x2 + x - 1)1 -(x2 + x - 1)1 (x2 + x - 1)1 xJ -(x2 + x - 1)1 + xJ xJ (x2 + x — 1)r 1 1 ( ) xJ (x2 + x - 1)1 - xJ (x2 + x - 1)r |(x2 + x - 1)1 - 2xJ| (x2 + x - 1)2r-1(x2 - (2r - 1)x - 1). In particular, we obtain Amin(Qr,r,2r) = —t. Since p < r and q < r, Qr,r,2r has an induced edge-signed subgraph isomorphic to Qp,q,r. By Lemma 2.23, Amin(Qp,qir) > Example 3.3. Let 7i and 72 be the edge-signed triangles having exactly one (+)-edge and exactly two (+)-edges, respectively, i.e., V(71) = V(72) = jvi, v2, v3}, E+(71) = E-(72) = {{vi,v2}}, and E-(71) = E+(72) = {{vi,v3}, {v2,v3}} (see Figure 4). For ei, £2, £3 € {1, —1} and S e {0, ±1}, let Si(ei, £2, £3), S2(£i,£2,S), £3(61, £2,S), and S4(£i, £2) be the edge-signed graphs in Figure 5, where an edge with label 1 (resp. —1) represents a (+)-edge (resp. a (—)-edge) and an edge with label 0 represents a non-adjacent pair. It can be checked that each of the edge-signed graphs 72, Si(£i, £2, £3), S2(£i, £2, S), S3(£i, £2, S), S4(£i, £2) has the smallest eigenvalue less than —t. Theorem 3.4. Let S be a connected edge-signed graph with Amin(S) > —t. Assume that S does not contain an induced edge-signed subgraph isomorphic to 7i. Then either S is isomorphic to Qp,q,r for some non-negative integers p, q, r with p + q < r, or S has at most 6 vertices and is isomorphic to one of the 15 edge-signed graphs in Figure 6. Proof. By using computer [14], we checked that the theorem holds when |V (S)| < 7. We prove the assertion by induction on | V(S) |. Assume that the assertion holds for | V(S) | = n (> 7). Suppose that |V (S)| = n + 1. It follows from Problem 6(a) in Section 6 of [9] that there exists a vertex v which is not a cut vertex of S. Then S — v is connected, where S — v is the edge-signed subgraph induced by V(S)\{v}. Since Amin(S — v) > Amin(S) > —t, the inductive hypothesis implies that S — v is isomorphic to Qp,q,r for some p, q, r with p + q + r = n. Thus S is the edge-signed graph obtained from Qp,q,r by adding the vertex v and signed edges between v and some vertices in Qp,q,r. Note that r > 4 since n = p + q + r > 7 and p + q < r. □ Figure 4: The edge-signed triangles 71 and 72 A. Munemasa et al.: Fat Hoffman graphs with smallest eigenvalue at least — 1 — t 255 Figure 5: Edge-signed graphs with smallest eigenvalue less than —t We claim that either v is adjacent to only one vertex of Vr, or to all the vertices of Vr. Note that S cannot contain any of the edge-signed graphs 72, Si(ei, e2, e3), S2(ei, e2, S), S3(ei, e2, S), S4(e1, e2) in Example 3.3. If v is adjacent to none of the vertices of Vr, then S contains S4(e1, e2) as an induced edge-signed subgraph, a contradiction. If the number of neighbors of v in Vr is at least 2 and less than r, then S contains S3(e1, e2, S) as an induced edge-signed subgraph, a contradiction. Thus the claim holds. Now, if v is adjacent to only one vertex of Vr, then the unique neighbor of v in Vr is in Vr \ (Up U Uq). Indeed, otherwise we would find S2(e1, e2, S) as an induced edge-signed subgraph, a contradiction. Also, v is adjacent to none of the vertices of Vp U Vq since otherwise we would find S1(e1, e2, e3) as an induced edge-signed subgraph, a contradiction. Thus S is isomorphic to Qp+1,q,r or Qp,q+1,r. Suppose that v is adjacent to all the vertices of Vr. Since Vr is a clique consisting of (+)-edges only, the assumption implies that v is incident with at most one (—)-edge to Vr. If there is a vertex of Vr joined to v by a (—)-edge, then we find 72 as an induced edge-signed subgraph, a contradiction. Thus all the edges from v to Vr are (+)-edges. Now v is adjacent to none of the vertices of Vp U Vq since otherwise we would find S3(e1, e2,0) as an induced edge-signed subgraph, a contradiction. Thus S is isomorphic to Qp,q,r+1. Hence the theorem holds. □ Lemma 3.5. The smallest eigenvalues of the signed adjacency matrices of the edge-signed graphs in Figure 6 are given as follows: Amin(S ) —%/2 1-^17 2 1+ t -1.414213 if Sg{S3,1, S4,4}, -1.561553 if S e {S4,5, S5,5, S5,6}, -1.601679 if S = S6,3, -1.618034 otherwise, —t 256 Ars Math. Contemp. 7(2014)247-262 # S3,1 & 4,5 i......: n & 4,1 4 4,2 & 4,3 4 4,4 5. 5,1 5 5,2 5. 5,3 5 5,4 5 5,5 —1 — t . ' □ Lemma 3.8. Let S be a connected edge-signed graph with three vertices. Let D be a 3 x 3 diagonal matrix with diagonal entries 1 or 2 such that at least one of the diagonal entries is 2. Then M (S) — D has the smallest eigenvalue less than —1 — Proof. This can be checked by a direct calculation. □ A. Munemasa et al.: Fat Hoffman graphs with smallest eigenvalue at least — 1 — t 257 Lemma 3.9. Let H be a fat indecomposable Hoffman graph with smallest eigenvalue at least — 1 — t . If some slim vertex of H has at least two fat neighbors, then the special graph S(H) of H is isomorphic to Qq,q,i, Qi,o,i, or Qo,i,i. Proof. In view of Lemma 2.6, it suffices to show that every fat indecomposable Hoffman graph with three slim vertices, in which some slim vertex has two fat neighbors, has the smallest eigenvalue less than —1 — t. Let H be such a Hoffman graph. Then S(H) is connected by Lemma 2.21 and B(H) = M(S(H)) — D for some diagonal matrix D with diagonal entries 1 or 2 such that at least one of the diagonal entries is 2. Then we have a contradiction by Lemma 3.8. □ Example 3.10. Let Hxvi and Hxvn be the Hoffman graphs in Figure 7. The special graphs of Hxvi and Hxvii are Qi,o,i and Qo,i,i, respectively, and Am;n(Hxvi) — Am;n (Hxvii) — — 1 — t . iUiV Hxvi Hxvii Figure 7: Fat indecomposable Hoffman graphs Lemma 3.11. Let H be a Hoffman graph in which every slim vertex has at most one fat neighbor Then the special graph S(H) of H does not contain an induced edge-signed subgraph isomorphic to Ti. Proof. Suppose that the special graph S(H) of H contains Ti = ({vi, v2, v3}, {{vi, v2}}, {{vi, v3}, {v2, v3}}) as an induced edge-signed subgraph. Since v3 is incident to a (—)-edge, v3 must have a fat neighbor. Since every slim vertex of H has at most one fat neighbor, v3 has a unique fat neighbor f. Then f is adjacent to vi and v2. This is a contradiction to {vi,v2}e E+(Ti). □ Lemma 3.12. Let H be a Hoffman graph in which every slim vertex has exactly one fat neighbor. If the special graph S(H) of H is isomorphic to Qp,q,r for some non-negative integers p, q, r, then H is an induced Hoffman subgraph of a Hoffman graph H' with Vs(H') = Vs(H) which has a decomposition {H®}r= such that Hl is isomorphic to Hxvi, Hxvii, or Hii for all i = 1,..., r. In particular, if r > 2, then H is ( — 1 — t)-reducible. Proof. By the assumption, Vs(H) = V(S(H)) is partitioned into VpU Vq U Vr as Definition 3.1. Consider the Hoffman graph H' defined by Vs(H') := Vs(H), Vf (H') := Vf (H) U {f*}, and E(H') := E(H) U {{v,f*} | v e Vr}, where f* is anew fat vertex. Note that H is an induced Hoffman subgraph of H' with Vs(H) = Vs(H). Then H' has a decomposition {Hi}r=i with H® = Hxvi for 1 < i < p, H® = Hxvii for p < i < p + q, and H® = Hii for p + q < i < p + q + r (see Examples 2.4 and 3.10). Since r > 2 and each of the Hoffman graphs H® has the smallest eigenvalue at least —1 — t, it follows that H is (—1 — t )-reducible. □ 258 Ars Math. Contemp. 7 (2014) 201-213 Theorem 3.13. Let H be a fat indecomposable Hoffman graph with smallest eigenvalue at least -1 - t. Then the following hold: (i) If some slim vertex of H has at least two fat neighbors, then the special graph S (H) ofH is isomorphic to Qo,o,i, Qi,o,i, or Qo,i,i. (ii) If every slim vertex of H has exactly one fat neighbor, then the special graph S(H) of H is isomorphic to Qp,q,r for some non-negative integers p, q, r with p + q < r or one of the 15 edge-signed graphs in Figure 6. Proof. The statement (i) follows from Lemma 3.9. We show (ii). Suppose that every slim vertex of H has exactly one fat neighbor. By Lemma 2.21, S(H) is connected, and by Lemma 2.25, S(H) has smallest eigenvalue at least -t. Moreover, by Lemma 3.11, S(H) does not contain an induced edge-signed subgraph isomorphic to 71 Now Theorem 3.4 implies that S (H) is isomorphic Qp,q,r or one of the 15 edge-signed graphs in Figure 6. □ Corollary 3.14. Let H be a fat (-1 - t)-irreducible Hoffman graph. Then the special graph S(H) of H is isomorphic to Q0,0,1, Q1,0,1, Q0,1,1, or one of the 15 edge-signed graphs in Figure 6. Proof. Since H is (-1 - t)-irreducible, H is indecomposable. If some slim vertex of H has at least two fat neighbors, then the statement holds by Theorem 3.13 (i). Suppose that every slim vertex of H has exactly one fat neighbor. By Theorem 3.13 (ii), S(H) is isomorphic to Qp,q,r for some non-negative integers p, q, r, or one of the 15 edge-signed graphs in Figure 6. Since H is (-1 - t)-irreducible, the former case occurs only for r =1 by Lemma 3.12. Hence the corollary holds. □ 3.3 The classification of fat Hoffman graphs with smallest eigenvalue at least — 1 — t V iYlYl h3,1 h4,1 H4,2 H4,3 H2 4,3 H1 4,4 H1 4,5 H2 4,5 Figure 8: The fat (-1 - t)-irreducible Hoffman graphs with 3 or 4 slim vertices Lemma 3.15. Let H be a fat indecomposable Hoffman graph with smallest eigenvalue at least -1 - t. If the number of slim vertices of H is at most two, then H is isomorphic to one of Hi, Hii, Hiii, Hiv, Hxvi, and Hxvii. A. Munemasa et al.: Fat Hoffman graphs with smallest eigenvalue at least — 1 — t 259 H1 5,1 H2 5,1 H3 5,1 H1 5,2 H1 5,3 H1 5,4 A H2 5,4 H3 5,4 H4 5,4 tC m> H1 5,5 H2 5,5 H3 5,5 H1 5,6 Figure 9: The fat (-1 - t)-irreducible Hoffman graphs with 5 slim vertices 260 Ars Math. Contemp. 7 (2014) 201-213 A. Munemasa et al.: Fat Hoffman graphs with smallest eigenvalue at least — 1 — t 261 Proof. Straightforward. □ Lemma 3.16. Let H be a fat (-1 - t )-irreducible Hoffman graph. If S (H) is isomorphic to Si,j in Figure 6, then H is isomorphic to Hk,j for some k in Figures 8, 9, and 10. Proof. By Lemma 3.9, every slim vertex has exactly one fat neighbor. It is then straightforward to establish the lemma. □ Theorem 3.17. Let H be a fat (-1 - t )-irreducible Hoffman graph. Then H is isomorphic to one of Hi, Hii, Hiii, Hxvi, Hxvii, and the 32 Hoffman graphs given in Figures 8, 9, and 10. Proof. By Corollary 3.14, the special graph S(H) of H is isomorphic to Qo,o,1, Q1,o,1, Qo,1,1, or one of the 15 edge-signed graphs in Figure 6. If the number of slim vertices of H is at most two, then the statement holds by Lemma 3.15 and Example 2.15. If the number of slim vertices of H is at least three, then the statement holds by Lemma 3.16. □ Theorem 3.18. Let H be the set of isomorphism classes of the maximal members of the 37 fat (-1 - t)-irreducible Hoffman graphs given in Theorem 3.17, with respect to taking induced Hoffman subgraphs. More precisely, H is the set of isomorphism classes of HXVi, HXVii, Hl,1, H4,3, Hs,2, H5,3, H5,6, and the 11 Hoffman graphs in Figure 10. Then every fat Hoffman graph with smallest eigenvalue at least -1 - t is an H-line graph. Proof. It suffices to show that every fat indecomposable Hoffman graph H with smallest eigenvalue at least -1 - t is an H-line graph. First suppose that some slim vertex of H has two fat neighbors. Then by Lemma 3.9, H has at most two slim vertices, and by Lemma 3.15, H is isomorphic to one of Hi, Hii, Hiii, Hiv, Hxvi, and Hxvii. Since Hi and Hn are induced Hoffman subgraphs of HXVi, and Hm is an induced Hoffman subgraph of HXVii, they are H-line graphs. Note that HiV is also an H-line graph since Example 2.15 shows that HiV is an induced Hoffman subgraph of a Hoffman graph having a decomposition into two induced Hoffman subgraphs isomorphic to Hi. Thus the result holds in this case. Next suppose that every slim vertex of H has exactly one fat neighbor. Then by Theorem 3.13 (ii), S(H) is isomorphic to Qp,q,r for some non-negative integers p, q, r with p + q < r or one of the 15 edge-signed graphs in Figure 6. In the former case, H is an H-line graph by Lemma 3.12. In the latter case, Lemma 3.16 implies that H is an H-line graph since H contains all the maximal members of the isomorphism classes of Hoffman graphs Hjfc,j. □ 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] P. J. Cameron, J. J. Seidel and S. V. Tsaranov, Signed graphs, root lattices, and Coxeter groups, J. Algebra 164 (1994), 173-209. [3] D. Cvetkovic, M. Doob and S. Simic, Generalized line graphs, J. Graph Theor. 5 (1981), 385399. [4] D. Cvetkovic, P. Rowlinson and S. K. Simic, Spectral Generalizations of Line Graphs — On graphs with least eigenvalue —2, Cambridge University Press, Cambridge, 2004. 262 Ars Math. Contemp. 7 (2014) 201-213 [5] A. J. Hoffman, On limit points of the least eigenvalue of a graph, Ars Combinatoria 3 (1977), 3-14. [6] A. J. Hoffman, On graphs whose least eigenvalue exceeds —1 — y/2, Linear Algebra Appl. 16 (1977), 153-165. [7] R. A. Horn and C. R. Johnson, Matrix Analysis, Corrected reprint of the 1985 original, Cambridge University Press, Cambridge, 1990. [8] 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. [9] L. Lovasz, Combinatorial Problems and Exercises, 2nd edition, North-Holland, 1993. [10] T. Taniguchi, On graphs with the smallest eigenvalue at least —1 — y/2, part I, Ars Math. Contemp. 1 (2008), 81-98. [11] T. Taniguchi, On graphs with the smallest eigenvalue at least —1 — \/2, part II, Ars Math. Contemp. 5 (2012), 239-254. [12] R. Woo and A. Neumaier, On graphs whose smallest eigenvalue is at least —1 — y/2, Linear Algebra Appl. 226-228 (1995), 577-591. [13] H. Yu, On the limit points of the smallest eigenvalues of regular graphs, Designs Codes Cryp-togr. 65 (2012), 77-88. [14] The Magma Computational Algebra System for Algebra, Number Theory and Geometry, URL: http://magma.maths.usyd.edu.au/magma/.