¿^creative , ars mathematica ^commons contemporánea Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 7 (2014) 105-121 On fat Hoffman graphs with smallest eigenvalue at least —3 Hye Jin Jang , Jack Koolen Department of Mathematics, POSTECH, Pohang 790-784, South Korea Akihiro Munemasa Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan Tetsuji Taniguchi Matsue College of Technology, Nishiikuma-cho 14-4, Matsue, Shimane 690-8518, Japan Received 31 October 2011, accepted 19 September 2012, published online 21 March 2013 Abstract We investigate fat Hoffman graphs with smallest eigenvalue at least -3, using their special graphs. We show that the special graph S(H) of an indecomposable fat Hoffman graph H is represented by the standard lattice or an irreducible root lattice. Moreover, we show that if the special graph admits an integral representation, that is, the lattice spanned by it is not an exceptional root lattice, then the special graph S-(H) is isomorphic to one of the Dynkin graphs An, Dn, or extended Dynkin graphs An or Dn. Keywords: Hoffman graph, line graph, graph eigenvalue, special graph, root system. Math. Subj. Class.: 05C50, 05C76 1 Introduction Throughout this paper, a graph will mean an undirected graph without loops or multiple edges. Hoffman graphs were introduced by Woo and Neumaier [5] to extend the results of Hoffman [3]. Hoffman proved what we would call Hoffman's limit theorem (Theorem 2.14) which asserts that, in the language of Hoffman graphs, the smallest eigenvalue of a fat Hoffman graph is a limit of the smallest eigenvalues of a sequence of ordinary graphs with increasing minimum degree. Woo and Neumaier [5] gave a complete list of fat indecomposable Hoffman graphs with smallest eigenvalue at least -1 - %/2. From their list, we E-mail addresses: laluz@postech.ac.kr (Hye Jin Jang), koolen@postech.ac.kr (Jack Koolen)munemasa@math.is.tohoku.ac.jp (Akihiro Munemasa), tetsuzit@matsue-ct.ac.jp (Tetsuji Taniguchi) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 106 ArsMath. Contemp. 7 (2014) 105-121 find that only -1, -2 and -1 - %/2 appear as the smallest eigenvalues. This implies, in particular, that -1, -2 and -1 - %/2 are limit points of the smallest eigenvalues of a sequence of ordinary graphs with increasing minimum degree. It turns out that there are no others between -1 and -1 - %/2. More precisely, for a negative real number A, consider the sequences n(A) = inf{Amin(r) | mindegr > k, Amin(r) > A} (k = 1, 2,...), 0 k, Amin(r) < A} (k = 1, 2,...), where r runs through graphs satisfying the conditions specified above, namely, r has minimum degree at least k and r has smallest eigenvalue greater than (or less than) A. Then Hoffman [3] has shown that lim n(-2) = -1, lim 0 1 is an injective mapping, a reduced representation of norm m may not be. See Section 4 for more details. Lemma 2.7. Let H be a Hoffman graph having a representation of norm m. Then H has a reduced representation of norm m, and A(H, m) is isomorphic to Ared(H, m) © Z|Vf as a lattice. Proof. Let ^ : V(H) ^ Rn be a representation of norm m. Let U be the subspace of Rn generated by j^(x) | x € Vf (H)}. Let p, p^ denote the orthogonal projections from Rn onto U, Urespectively. Then p^ o ^ is a reduced representation of norm m, p^(A(H,m)) = Ared(H,m),andp(A(H,m)) ^ Z|Vf)|. □ Theorem 2.8. For a Hoffman graph H, the following conditions are equivalent: (i) H has a representation of norm m, (ii) H has a reduced representation ofnorm m, (iii) Amin(H) > —m. Proof. From Lemma 2.7, we see that (i) implies (ii). Let ^ be a reduced representation of H of norm m. Then the matrix B(H) + ml is the Gram matrix of the image of and hence positive semidefinite. This implies that B(H) has smallest eigenvalue at least —m and hence Amin(H) > —m. This proves (ii) (iii). The proof of equivalence of (i) and (iii) can be found in [5, Theorem 3.2]. □ From Theorem 2.8, we obtain the following lemma: H. J. Jang et al.: On fat Hoffman graphs with smallest eigenvalue at least —3 109 Lemma 2.9. If G is a subgraph of a Hoffman graph H, then Amin(G) > Amin(H) holds. Proof. Let m := -Amin(H). Then H has a representation ^ of norm m by Theorem 2.8. Restricting ^ to the vertices of G we obtain a representation of norm m of G, which implies Amin(G) > -m by Theorem 2.8. □ In particular, if r is the slim subgraph of H, then Amin(r) > Amin(H). Under a certain condition, equality holds in Lemma 2.9. To state this condition we need to introduce decompositions of Hoffman graphs. This was formulated first by the third author [4], although it was already implicit in [5]. Definition 2.10. Let H be a Hoffman graph, and let H1 and H2 be two non-empty induced Hoffman subgraphs of H. The Hoffman graph H is said to be the sum of H1 and H2, written as H = H1 W H2, if the following conditions are satisfied: (i) V(H) = V(H1) u V(H2); (ii) {Vs(H1), Vs (H2)} is a partition of VS(H); (iii) if x e Vs(Hi), y G Vf (H) and x ~ y, then y e Vf (H4); (iv) if x e Vs(H1), y G 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 = H1 W H2 for some non-empty subgraphs H1 and H2, then we call H decomposable. Otherwise H is called indecomposable. Clearly, a disconnected Hoffman graph is decomposable. It follows easily that the above-defined sum is associative and so that the sum n h = y H ¿=1 is well-defined. The main reason for defining the sum of Hoffman graphs is the following lemma. Lemma 2.11. Let H be a Hoffman graph and let H1 and H2 be two (non-empty) induced Hoffman subgraphs of H satisfying (i)—(iii) of Definition 2.10. Let ^ be a reduced representation of H of norm m. Then the following are equivalent. (i) H = H1 W H2, (ii) (^(x),^(y)) = 0 for any x e VS(H1) and y G VS(H2). Proof. This follows easily from the definitions of H = H1 W H2 and a reduced representation of norm m. □ Lemma 2.12. If H = H1 W H2, then Amin(H) = min{Amin(H1), Amin(H2)}. Proof. Let m = - min{Amin(H1), Amin(H2)}. In view of Lemma 2.9 we only need to show that Amin(H) > —m. By Theorem 2.8, H4 has a reduced representation ^ : V(H4) ^ Rni of norm m, for each i = 1,2. Define ^ : V(H) ^ Rni 0 Rn2 by ^(x) = ^1(x) 0 0 if x e V(H1), ^(x) =0 © ^2(x) otherwise. It is easy to check that ^ is a reduced representation of norm m, and the result then follows from Theorem 2.8. □ 106 ArsMath. Contemp. 7 (2014) 110-121 2.2 Hoffman's limit theorem In this subsection, we state and prove Hoffman's limit theorem (Theorem 2.14) using the concept of Hoffman graphs. Lemma 2.13. Let G be a Hoffman graph whose vertex set is partitioned as V U V2 U V3 such that (i) V U V3 c VS(G), (ii) there are no edges between Vi and V3, (iii) every pair of vertices x G V2 and y G V3 are adjacent, (iv) V3 is a clique. Let H be the Hoffman graph with the set of vertices Vi U V2 together with a fat vertex f G V (G) adjacent to all the vertices of V2. If G has a representation of norm m, then H has a representation of norm , (m - 1)|V2| m + |V3| + m - 1 • Proof. Let ^ : V(G) ^ Rd be a representation of norm m, and let fPv P = I P2 be the | V(G) | x d matrix whose rows are the images of V(G) = Vi U V2 U V3 under Set u = — \ A (¿(x) V|V3|(|V3| + m - 1) ¿V- «1 = 1 — > ^ jVsj + m - 1' I m — 1 £2 : _ jV3j + m — 1" Let j denote the row vector of length | V21 all of whose entries are 1. Then uuT = 1, (2.1) P1uT = 0, (2.2) P2 uT = (1 — £i)jT, (2.3) £2 = 2£1 — £2. (2.4) Fix an orientation of the complete digraph on V2, and let B be the |V2| x (|V221) matrix defined by Ba,(ß,7) = Saß — öa7 (a,ß,Y G V2, ß = Y). Then BBt = jV2j1 — J. (2.5) H. J. Jang et al.: On fat Hoffman graphs with smallest eigenvalue at least —3 111 We now construct the desired representation of H, as the row vectors of the matrix Pi 0 D = ( P2 + eijTu 0 C2B u 0 0 Then, using (2.1)-(2.5), we find Pi £2 VF2|1 0 P2 + £1 jT U 0 £2B u 0 0 DDT pT 0 P2T + £iUTj UTN 0 £2B T ^PiPiT + e2|V2|/ P2PT 0 fPi PT + e2|V2|1 PiPT P2PT + (2ei - e? )J + £2(|V211 - J) j Pi PT P2PT P2P2T + e2 |V2|1 jT 2Pi 0 'P1PT P?P2T 1 P1 P1 P2 P2PT P2PT 0 2p2 j // 0 0> j 1 + e2|V2| (0 I 0 1 / \0 0 0> 0 •T Therefore, the row vectors of D define a representation of norm m + e21V21 of the Hoffman graph H. □ Theorem 2.14 (Hoffman). Let H be a Hoffman graph, and let /,...,/ G Vf (H). Lei ©ni,.,nfc be the Hoffman graph obtained from H by replacing each f by a slim n-clique Kj, and joining all the neighbors of / with all the vertices of Kj by edges. Then Amin(©ni—nk) > Amin(H), (2.6) and lim Amin (0ni ,...,nk )= Amin(H). ni (2.7) Proof. We prove the assertions by induction on k. First suppose k = 1. Let Mn = —Amin(©n). Let Hn denote the Hoffman graph obtained from H by attaching a slim n-clique K to the fat vertex /i, joining all the neighbors of /i and all the vertices of K by edges. Then Hn contains both H and ©n as subgraphs, and Hn = H W H', where H' is the subgraph induced on K U {/}. Since Amin(H') = —1, Lemma 2.12 implies Amin(H) = Amin(Hn) < Amin(©n) = — Mn. Thus (2.6) holds for k = 1. Since n is arbitrary and {—is decreasing, we see that limn^TO Mn exists and Amin(H) < — lim Mn. (2.8) Since ©n has a representation of norm Mn, it follows from Lemma 2.13 that H has a representation of norm (Mn — 1)|Nh(/)| Mn +--:-:-. n + Mn — 1 0 1 j 0 1 j 106 ArsMath. Contemp. 7 (2014) 112-121 By Theorem 2.8, we have A (H) . (Mn - 1)nh(/)| Amin ) > - Mn--;-;-, n + Mn - 1 which implies Amin(H) > - lim Mn. (2.9) n—^^o Combining (2.9) with (2.8), we conclude that (2.7) holds for k = 1. Next, suppose k > 2. Let ©ni1 be the Hoffman graph obtained from H by replacing each / (1 < i < k - 1)bya slim n4-clique K\ and joining all the neighbors of / with all the vertices of Kl by edges. Then ©ni> ->nk is obtained from ©ni> ->nk-1 by replacing /k by a slim nk-clique Kk, and joining all the neighbors of /k with all the vertices of Kk by edges. Then it follows from the assertions for k =1 that Amin(©ni""'nfc ) > Amin(©ni"'"nfc-1 ), (2.10) and lim Amin(©ni""'nfc ) = Amin (©ni '"''nfc_1 ). This means that, for any e > 0, there exists N such that nk > Ni 0 < Amin(©ni"'"nfc ) - Amin (Gni '''''nk_1 ) < e. By induction, we have Amin (G^"'"^-1 ) > Amin(H), (2.11) and lim Amin (©ni"'"nk-1 ) = Amin(H). (2.12) ni ,'",nfc_ i —to Combining (2.10) with (2.11), we obtain (2.6), while (2.11) and (2.12) imply that there exists N0 such that ni, . . . , nk-1 > No 0 < Amin (©ni"'"nk_1 ) - Amin(H) < e. Setting N = max{N0, N1}, we see that ni,...,nk > N 0 < Amin(©ni"'"nfc ) - Amin(H) < 2e. This establishes (2.7). □ Corollary 2.15. Let H be a Hoffman graph. Let rn be the slim graph obtained from H by replacing every fat vertex / of H by a slim n-clique K (/), and joining all the neighbors of / with all the vertices of K(/) by edges. Then Amin (rn) > Amin (H), H. J. Jang et al.: On fat Hoffman graphs with smallest eigenvalue at least —3 113 and lim Amin(rn) = Amin(H). In particular, for any e > 0, there exists a natural number n such that, every slim graph A containing rn as an induced subgraph satisfies Amin(A) < Amin(H) + e. Proof. Immediate from Theorem 2.14. □ 3 Special graphs of Hoffman graphs Definition 3.1. Let ^ be a real number with ^ < — 1 and let H be a Hoffman graph with smallest eigenvalue at least Then H is called saturated if no fat vertex can be attached to H in such a way that the resulting graph has smallest eigenvalue at least Proposition 3.2. Let ^ be a real number, and let H be a family of indecomposable fat Hoffman graphs with smallest eigenvalue at least ^. The following statements are equivalent: (i) every fat Hoffman graph with smallest eigenvalue at least ^ is a subgraph of a graph H = i±i n ==1 H® such that H® is a member of H for all i — 1,... ,n. (ii) every saturated indecomposable fat Hoffman graph is isomorphic to a subgraph of a member of H. Proof. First suppose (i) holds, and let H be a ^-saturated indecomposable fat Hoffman graph. Then H is a fat Hoffman graph with smallest eigenvalue at least hence H is a subgraph of H' — 1+1n=1 H®, where H® is a member of H for i — 1,..., n. Since H is ^-saturated, it coincides with the subgraph ((Vs (H)))h' of H'. Since H is indecomposable, this implies that H is a subgraph of H® for some i. Next suppose (ii) holds, and let H be a fat Hoffman graph with smallest eigenvalue at least Without loss of generality we may assume that H is indecomposable and saturated. Then H is isomorphic to a subgraph of a member of H, hence (i) holds. □ Definition 3.3. For a Hoffman graph H, we define the following three graphs S-(H), S+(H) and S(H) as follows: For e G {-, +} define the special e-graph Se — (Vs(H),Ee) as follows: the set of edges Ee consists of pairs {s1, s2} of distinct slim vertices such that sgn(^(s1), -0(s2)) — e, where ^ is a reduced representation of H of norm m. The graph S (H) :— S +(H) US- (H) — (Vs(H),E- U E+) is the special graph of H. Note that the definition of the special graph S (H) is independent of the choice of the norm m of a reduced representation It is easy to determine whether a Hoffman graph H is decomposable or not. Lemma 3.4. Let H be a Hoffman graph. Let Vs(H) — V1 U V2 be a partition, and set H® — ((V®))h for i — 1, 2. Then H — H1 W H2 if and only if there are no edges connecting V1 and V2 in S (H). In particular, H is indecomposable if and only if S (H) is connected. Proof. This is immediate from Definition 2.10(iv) and Definition 3.3. □ 106 ArsMath. Contemp. 7 (2014) 114-121 A A H(1), Amin = -1 H(2), Amin = -2 H(3), Amin = -3 Figure 1. For an integer t > 1, let H(t) be the fat Hoffman graph with one slim vertex and t fat vertices. Lemma 3.5. Let t be a positive integer. If H is a fat Hoffman graph with Amin(H) > —t containing H(t) as a Hoffman subgraph, then H = H(t) W H' for some subgraph H' of H. In particular, if H is indecomposable, then H = H(t). Proof. Let x be the unique slim vertex of H(t). Let ^ be a reduced representation of norm t of H. Then ^(x) = 0, hence x is an isolated vertex in S(H). Thus H = H(t) W ((VS(H) \ |x}))h by Lemma 3.4. □ Lemma 3.6. Let H be a fat Hoffman graph with smallest eigenvalue at least —3. Let ^ be a reduced representation of norm 3 of H. Then for any distinct slim vertices x, y of H, (V>(x),V(y)) e{1,0, —1}. Proof. Since H is fat, we have (^(x),^(x)) < 2 for all x G Vs(H). Thus |(^(x), ^(y))| < 2 for all x, y G Vs(H) by Schwarz's inequality. Equality holds only if ^(x) = ±^(y) and (^(x),^(x)) = 2. The latter condition implies |Nf (x)| = 1, hence |Nf (x, y)| < 1. Thus (^(x), ^(y)) > —1, while (^(x), ^(y)) = 2 cannot occur unless x = y, by Definition 2.6. Therefore, | (^(x), ^(y)) | < 2, and the result follows. □ Let H be a fat Hoffman graph with smallest eigenvalue at least —3. Then by Lemma 3.6, the edge set of the special graph Se(H) is {{x,y} | x, y G Vs(H), (^(x),^(y)) = e1}, for e G {+, —}. Theorem 3.7. Let H be a fat indecomposable Hoffman graph with smallest eigenvalue at least —3. Then every slim vertex has at most three fat neighbors. Moreover, the following statements hold: (i) If some slim vertex has three fat neighbors, then H = H(3). (ii) If no slim vertex has three fat neighbors and some slim vertex has exactly two fat neighbors, then Ared(H, 3) ~ Zn for some positive integer n. (iii) If every slim vertex has a unique fat neighbor, then Ared(H, 3) is an irreducible root lattice. H. J. Jang et al.: On fat Hoffman graphs with smallest eigenvalue at least —3 115 Proof. As the smallest eigenvalue is at least -3, every slim vertex has at most three fat neighbors. If |Nf (x)| = 3 for some slim vertex x of H, then H contains H(3) as a subgraph. Thus H = H(3) by Lemma 3.5, and (i) holds. Hence we may assume that |Nf (x)| < 2 for all x G Vs(H). Then for each x G Vs(H) we have ||^(x)||2 = 1 (resp. 2) if and only if |Nf (x)| = 2 (resp. |Nf (x)| = 1). Suppose that Ared(H, 3) contains m linearly independent vectors of norm 1. We claim that Ared(H, 3) can be written as an orthogonal direct sum Zm © A', where A' is a lattice containing no vectors of norm 1. Indeed, if x is a slim vertex such that ||^(x) ||2 = 2 and ^(x) G Zm, then ^(x) is orthogonal to Zm. This implies Ared(H, 3) = Zm © A' and ^(VS(H)) C Zm U A'. If m > 0 and A' = 0, then the special graph S (H) is disconnected. This contradicts the indecomposability of H by Lemma 3.4. Therefore, we have either m = 0 or A' = 0. In the latter case, (ii) holds. In the former case, Ared(H, 3) = A' is generated by vectors of norm 2, hence it is a root lattice. Again by the assumption and Lemma 3.4, (iii) holds. □ We shall see some examples for the case (ii) of Theorem 3.7 in the next section. As for the case (iii), Ared(H, 3) is an irreducible root lattice of type An, Dn or En. If Ared(H, 3) is not an irreducible root lattice of type En, then it can be imbedded into the standard lattice, hence the results of the next section applies. On the other hand, if Ared(H, 3) is an irreducible root lattice of type En, then it is contained in the irreducible root lattice of type E8, and hence there are only finitely many possibilities. For example, Let r be any ordinary graph with smallest eigenvalue at least -2 (see [1] for a description of such graphs). Attaching a fat neighbor to each vertex of r gives a fat Hoffman graph with smallest eigenvalue at least -3. However, this Hoffman graph may not be maximal among fat Hoffman graphs with smallest eigenvalue at least -3. Therefore, we aim to classify fat Hoffman graphs with smallest eigenvalue at least -3 which are maximal in E8. This may seem a computer enumeration problem, but it is harder than it looks. Example 3.8. Let n denote the root system of type E8. Fix a G n. Then there are elements Pi G n (i = 1,..., 28) such that 28 {P G n | (a,P) = 1} = J{Pi, a - A}. i=i Let V denote the set of 57 roots consisting of the above set and a. Then V is a reduced representation of a fat Hoffman graph H with 29 fat vertices. The fat vertices of H are fi (i = 0,1,..., 28), f0 is adjacent to a, and fi is adjacent to Pi, a - Pi (i = 1,..., 28). It turns out that H is maximal among fat Hoffman graphs with smallest eigenvalue at least -3. Indeed, no fat vertex can be attached, since the root lattice of type E8 is generated by V \ {y} for any y g V, and attaching another fat neighbor to y would mean the existence of a vector of norm 1 in the dual lattice Eg of E8. Since Eg = E8, there are no vectors of norm 1 in Eg. This is a contradiction. If a slim vertex can be attached, then it can be represented by S G n with (a, S) = 0. Then there exists i G {1,..., 28} such that (Pi, S) = ±1. Exchanging pi with a - pi if necessary, we may assume (Pi, S) = -1. This implies that Pi and S have a common fat neighbor. Since (Pi, a - Pi) = -1, pi and a - pi have a common fat neighbor. Since Pi has a unique fat neighbor, S and a - Pi have a common fat neighbor, contradicting (S, a - Pi) = 1. 106 ArsMath. Contemp. 7 (2014) 116-121 On the other hand, it is known that there is a slim graph r with 36 vertices represented by the root system of type E8 (see [1]). Attaching a fat neighbor to each vertex of r gives a fat Hoffman graph H' with smallest eigenvalue -3 such that Ared(H', 3) is isometric to the root lattice of type E8. The graph H' is not contained in H, so there seems a large number of maximal fat Hoffman graphs represented in the root lattice of type E8. 4 Integrally represented Hoffman graphs In this section, we consider a fat (-3)-saturated Hoffman graph H such that Ared(H, 3) is a sublattice of the standard lattice Zn. Since any of the exceptional root lattices E6, E7 and E8 cannot be embedded into the standard lattice (see [2]), this means that, in view of Theorem 3.7, Ared(H, 3) is isometric to Zn or a root lattice of type An or Dn. Note that Ared(H, 3) cannot be isometric to the lattice Ai, since this would imply that H has a unique slim vertex with a unique fat neighbor, contradicting (-3)-saturatedness. The following example gives a fat (-3)-saturated graph H with Ared(H, 3) = Z. Example 4.1. Let H be the Hoffman graph with vertex set Vs(H) U Vf (H), where Vs(H) = Z/4Z, Vf (H) = {f | i € Z/4Z}, and with edge set {{0, 2}, {1, 3}} U {{i, fj} | i = j or j + 1}. Then H is a fat indecomposable (-3)-saturated Hoffman graph such that Ared(H, 3) is isomorphic to the standard lattice Z. Since S-(H) has edge set {{i, i + 1} | i € Z/4Z}, S- (H) is isomorphic to the Dynkin graph A3. Theorem 4.9 below implies that H is maximal, in the sense that no fat indecomposable (-3)-saturated Hoffman graph contains H. For the remainder of this section, we let H be a fat indecomposable (-3)-saturated Hoffman graph such that Ared(H, 3) is isomorphic to a sublattice of the standard lattice Zn. Let ^ be a representation of norm 3 of H. Then we may assume that ^ is a mapping from V(H) to Zn © ZVf (h), where its composition with the projection Zn ©ZVf (h) ^ Zn gives a reduced representation ^ : Vs(H) ^ Zn. It follows from the definition of a representation of norm 3 that ^(s) = Y^ ef, f e«H (s) n ^(s) = Y1 ^(s)j ej, j=i ^(s)j €{0, ±1}, and |{j | j € {1,. .. ,n}, ^(s)j € {±1}}| = 3 - |Nf (s)| < 2. (4.1) Lemma 4.2. If i € {1,...,n} and ^(s)i = 0 for some s € Vs(H), then there exist si, s2 € Vs(H) such that ^(si)i = -^(s2)i = 1. Proof. By way of contradiction, we may assume without loss of generality that i = n, and ^(s)n € {0,1} for all s € Vs(H). Let © be the Hoffman graph obtained from H by attaching anew fat vertex g and join it to all the slim vertices s of H satisfying ^(s)n = 1. Then the composition of ^ : Vs(H) = Vs (©) ^ Zn and the projection Zn ^ Zn-i gives a reduced representation of norm 3 of ©. By Theorem 2.8, © has smallest eigenvalue at least -3. This contradicts the assumption that H is (-3)-saturated. □ H. J. Jang et al.: On fat Hoffman graphs with smallest eigenvalue at least —3 117 Proposition 4.3. The graph S (H) is connected. Proof. Before proving the proposition, we first show the following claim. Claim 4.4. Let s1 and s2 be two slim vertices such that ^(s1)i = 1 and ^(s2)i = —1 for some i G {1,..., n}. Then the distance between s1 and s2 is at most 2 in S-(H). By (4.1), we have (^(s1), ^(s2)) G {0, —1}. If (^(s1), ^(s2)) = —1, then s1 and s2 are adjacent in S- (H ) by the definition, hence the distance equals one. If ( ^(s1),^(s2)) = 0, then there exists a unique j G {1,..., n} such that ^(s1)j- = ^(s2)j = ±1. From Lemma 4.2, there exists a slim vertex s3 such that ^(s3)j = —^(s1)j-. If ^(s3)i = 0, then (^(sq), ^(s3)) G {±2} for some q G {1, 2}, which is a contradiction. Hence ^(s3)i = 0. This implies that (^(si),^(s3)) = —1 for i = 1,2, or equivalently, s3 is a common neighbor of s1 and s2 in S-(H). This shows the claim. Since H is indecomposable, S (H) is connected by Lemma 3.4. Thus, in order to show the proposition, we only need to show that slim vertices s1 and s2 with (^(s1), ^(s2)) = 1 are connected by a path in S-(H). There exists i G {1,... ,n} such that ^(s1)i = ^(s2)i = ±1. From Lemma 4.2, there exists a slim vertex s3 such that ^(s3)i = —^(s1 )i, and hence the distances between s 1 and s3 and between s3 and s2 are at most 2 in S- (H ) by Claim 4.4. Therefore, s 1 and s2 are connected by a path of length at most 4 in S- (H ). □ Lemma 4.5. Let H be a fat indecomposable (—3)-saturated Hoffman graph. Then the reduced representation of norm 3 of H is injective unless H is isomorphic to a subgraph of the graph given in Example 4.1. Proof. Suppose that the reduced representation ^ of norm 3 of H is not injective. Then there are two distinct slim vertices x and y satisfing ^(x) = ^(y). Then (^(x), ^(y)) = 0 or 1 . If (^(x), -0(y)) = 0, then ^(x) = ^(y) = 0, hence both x and y are isolated vertices, contradicting the assumption that H is indecomposable. Suppose (^(x), -0(y)) = 1. Since S-(H) is connected by Proposition 4.3, there exists a slim vertex z such that (^(x), ^(z)) = —1. Then we may assume ^(x) = e1 + efl + e/2, ^(y) = e1 + e f 3 + e f 4, ^(z) = —e1 + efi + ef3. If H has another slim vertex w, then ^M = -e1 + ef2 + ef4> and no other possibility occurs. Therefore, H is isomorphic to either the graph given in Example 4.1, or its subgraph obtained by deleting one slim vertex. □ Lemma 4.6. Suppose that s G Vs (H) has exactly two fat neighbors in H. Then the following statements hold. (i) for each f G Nf (s), |N5-(h)(s) n Nf(f )| < 2, (ii) |Ns- (h) (s) | < 4, and if equality holds, then S -(H) is isomorphic to the graph D 4, 106 ArsMath. Contemp. 7 (2014) 118-121 (iii) if \NS-(h) (s) | = 3, then two of the vertices in Ns-(h)(s) have s as their unique neighbor in S- (H). Proof. Let ^ be the reduced representation of norm 3 of H. Since s has exactly two fat neighbors, (^(s), ^(s)) = 1. This means that we may assume without loss of generality ^(s) = ei. Let f e Nh(s). If t i and ¿2 are distinct vertices of Ns-(h)(s) n NjS (f),then 1 > (0(ti),0(i2)) > (^(ti)+ ef ,^(¿2)+ ef) = (V>(ti ),^(t2)) + 1, Thus we have (^(t1), ^(t2)) < 0. Since t1,t2 e Ns-(h)(s), we have (^(s),^(t1)) = (^(s), -0(t2)) = -1, and hence we may assume without loss of generality that V>(ti) = -ei + e2, (4.2) ^(¿2) = -ei - e2. (4.3) Now it is clear that there cannot be another t3 e Ns-(h)(s). Thus \NS- (h)(s) n N^ (f)\ < 2. This proves (i). As for (ii), let Nf (s) = {f, f'}. Then \Ns-(h )(s)\ < \Ns-(h)(s) n NS(f)\ + \Ns-(h)(s) n NS(f')\ < 4 by (i). To prove (iii) and the second part of (ii), we may assume that {ti, ¿2} — Ns-(h)(s)n Nh (f). We claim that neither ti nor t2 has a neighbor in S-(H) other than s. Suppose by contradiction, that t3 = s is a neighbor in S-(H) of ti. By (4.2) (resp. (4.3)), f is the unique fat neighbor of ti (resp. t2). In particular, f is also a neighbor of t3. Observe 1 > (¿(sU(t3)) > (^(s),^(t3)) + 1, 1 > (¿(¿i), ¿(¿3)) = (^(ti), ^(¿3)) + 1 (i =1, 2). Thus (ei,^(t3)) < 0, (-ei ± e2,V(t3)) < 0. These imply (ei,^)) = ^,^(¿3)) = 0. But then -1 = (V>(ti), ^(¿3)) = (-ei + e2, ^(t3)) = 0. This is a contradiction, and we have proved our claim. Now (iii) is an immediate consequence of this claim. Continuing the proof of the second part of (ii), if \NS- (h ) (s) \ =4, then we may assume ^(¿i) = -ei + e3, ^(¿2) = -ei - e3, where {¿i,¿2} = Ns-(h)(s) n N^(f'). It follows that ti,t2,t'i,t2 are pairwise non-adjacent in S-(H). By our claim, none of ti,t2,t'i,t2 is adjacent to any vertex other than s in S-(H). Since S-(H) is connected by Proposition 4.3, S-(H) is isomorphic to the graph D 4. □ H. J. Jang et al.: On fat Hoffman graphs with smallest eigenvalue at least —3 119 Lemma 4.7. Suppose that slim vertices s,t+,t share a common fat neighbor and that they are represented as ^(s) = ei + e2, ^(t±) = -ei ± e3. If there exists a slim vertex t with ^(t) = —e2 + ej for some j G {1, 2, 3}, then the vertices t± have s as their unique neighbor in S- (H). Proof. Note that each of the vertices s,t±,t has a unique fat neighbor. Since (^(s), ^(t±)) = (^(s), -0(t)) = —1, these vertices share a common fat neighbor f. Suppose that there exists a slim vertex t' adjacent to t- in S-(H). This means (^(t'), ^(t-)) = —1. Since f is the unique fat neighbor of t-, t' is adjacent to f, and hence (^(t'), ^(u)) < 0 for u G {t,t+, s}. This is impossible. Similarly, there exists no slim vertex adjacent to t+ in S-(H). □ Lemma 4.8. Suppose that s G Vs(H) has exactly one fat neighbor in H. Then the following statements hold: (i) |NS- (h) (s) | < 4, and if equality holds, then S -(H) is isomorphic to the graph D 4, (ii) if |Ns-(h)(s)| = 3, then two of the vertices in Ns-(h)(s) have s as their unique neighbor in S-(H). Proof. Let ^ be the reduced representation of norm 3 of H. Since s has exactly one fat neighbor, (^(s), ^(s)) = 2. This means that we may assume without loss of generality ^(s) = e1 + e2. Let f be the unique fat neighbor of s. If t G NS- (h)(s), then t is adjacent to f, hence ^(t) G {—e1, —e2} U {—e, ± ej | 1 < i < 2 < j < n}. (4.4) If t,t' G NS-(h)(s) are distinct, then 1 > (¿(t),#t')) > (^(t)+ ef ,V(t') + ef) = (V>(t),V(t')) + 1, Thus we have (^(t),^(t')) < 0. If |NS-(^)(s)| > 3, then by (4.4), we may assume without loss of generality that there exists t g Ns-(h)(s) with ^(t) = —e1 + e3. Then ^(NS- (h) (s) \ {t}) is contained in {—e2 — e3}, {—e2, —ei — e3}, or {—ei — e3} U {—e2 ± ej} for some j with 3 < j < n. Thus |NS-(h)(s)| < 4, and equality holds only if ^(Ns-(h) (s)) = {—ei ± e3, —e2 ± ej} for some j with 3 < j < n. In this case, Lemma 4.7 implies that each of the vertices in Ns-(h)(s) has s as a unique neighbor. This means that S- (H) contains a subgraph 106 ArsMath. Contemp. 7 (2014) 120-121 isomorphic to the graph D4 as a connected component. Since S-(H) is connected by Proposition 4.3, we have the desired result. To prove (ii), suppose |Ns-(h)(s)| = 3. Then we may assume without loss of generality that Ns-(h)(s) = {t,t+,t-}, where ^(t±) = -e2 ± e4. Then by Lemma 4.7, the vertices t± have s as their unique neighbor in S- (H). □ Theorem 4.9. Let H be a fat indecomposable (-3)-saturated Hoffman graph such that Ared(H, 3) is isomorphic to a sublattice of the standard lattice Zn. Then S -(H) is a connected graph which is isomorphic to Am, Dm, Am or Dm for some positive integer m. Proof. From Proposition 4.3, S-(H) is connected. First we suppose that the maximum degree of S-(H) is at most 2. Then S-(H) = Am or S-(H) = Am for some positive integer m. Next we suppose that the degree of some vertex s in S-(H) is at least 3. From Lemma 4.6(ii) and Lemma 4.8(i), degs-(h)(s) < 4, and S -(H) = D 4 if degs-(h)(s) = 4. Thus, for the remainder of this proof, we suppose that the maximum degree of S- (H) is 3 and deg5-(h) (s) = 3. It follows from Lemma 3.5 that if H has a subgraph isomorphic to H(3), then H = H(3), in which case S- (H) consists of a single vertex, and the assertion holds. Hence it remains to consider two cases: s is adjacent to exactly two fat vertices, and s is adjacent to exactly one fat vertex. In either cases, by Lemma 4.6(iii) or Lemma 4.8(ii), s has at most one neighbor t with degree greater than 1. Thus, the only way to extend this graph is by adding a slim neighbor adjacent to t. We can continue this process, but once we encounter a vertex of degree 3, then the process stops by Lemma 4.6(iii) or Lemma 4.8(ii). Thus, S-(H) is isomorphic to one of the graphs Dm or Dm. □ Example 4.10. Let ni,..., nk be positive integers satisfying n > 2 for 1 < i < k. Set mj = J2¿=i n and lj = mj - j for j = 0,1,..., k. Let H be the Hoffman graph with Vs(H) = {vi | i = 0,1,..., mfc}, Vf (H) = {fj | j =0,1,..., k + 1}, and E(H) ={{vi, Vj/} | 1 < j < k, mj-i < i + 1 < i' < mj} u {{vmj-i, Vmj + i} | 1 < j < k} u {{fj,Vj} | 1 < j < k, mj-i < i < mj} u {{fo,vo}, {ffc+i,vmfc}}. Then H is a fat Hoffman graph with smallest eigenvalue at least -3, and S- (H) is isomorphic to the Dynkin graph Amfc+i. Indeed, H has a reduced representation ^ of norm 3 defined by ^(v ) = ( —1)je£j if i = mj, 0 < j < k, ( —1)j(ej_j — ej_j_i) if mj < i < mj+i, 0 < j < k. Moreover, H is (—3)-saturated. Indeed, suppose not, and let H be a Hoffman graph obtained by attaching a new fat vertex f to H, and let ^ be a reduced representation of norm 3 of H. If f is adjacent to vmj for some j G {0,1,...,k}, then vmj has three fat neighbors in H, hence ^(vmj ) = 0. This is absurd, since (^(vmj ), ^(vmj±1)) = —1. If f is adjacent to vj with mj-i < i < mj, then ||^(vi)|| = 1. Since (^(vj-i), ^(v»)) = (^K+i), ^K)) = H. J. Jang et al.: On fat Hoffman graphs with smallest eigenvalue at least —3 121 -1 while (V>(vj-i), V>(vi+i)) = 0, we may assume ^(vm) = ei ± e2, tp(vi) = —ei. Then i +1 < mj, and 0 = (i/S(vi+2),i/j(vi_i)) = (^A(vi+2), ei - e2) = (i'(vi+2), 2ei - (ei + e2)) = -2(V>(vi+2),4>(vi)) - (^^(vi+2),V'(vi+i)) = 1, which is absurd. We note that the graph S + (H) has the following edges: |{vm,--i,vm.+i} | 1 < j < k}. Example 4.11. Let H be the Hoffman graph constructed in Example 4.10 by setting ni = 1, n2 = 2, and n3 = 1. Let Ho (resp. Hi) be the Hoffman graph obtained from H by identifying the fat vertices f4 and f0 (resp. f4 and fi), and adding edges {v0, v2}, {v2, v4}. Then H0 and Hi are fat (-3)-saturated Hoffman graphs and S-(Hi) is isomorphic to the Dynkin graph A5 for i = 0,1. We note that S +(Hi) has two edges {v0, v2}, {v2, v4}. Examples 4.10 and 4.11 indicate that H is not determined by S± (H). We plan to discuss the classification of fat indecomposable (-3)-saturated Hoffman graphs with prescribed special graph in subsequent papers. References [1] D. Cvetkovic, P. Rowlinson and S. K. Simic, Spectral Generalizations of Line Graphs — On Graphs with Least Eigenvalue — 2, Cambridge Univ. Press, 2004. [2] W. Ebeling, Lattices and Codes, Vieweg, 2nd ed. Friedr. Vieweg & Sohn, Braunschweig, 2002. [3] A. J. Hoffman, On graphs whose least eigenvalue exceeds —1 — \[2, Linear Algebra Appl. 16 (1977), 153-165. [4] T. Taniguchi, On graphs with the smallest eigenvalue at least — 1 — \[2, part I, Ars Math. Con-temp. 1 (2008), 81-98. [5] R. Woo and A. Neumaier, On graphs whose smallest eigenvalue is at least —1 — \[2, Linear Algebra Appl. 226-228 (1995), 577-591 . [6] H. Yu, On the limit points of the smallest eigenvalues of regular graphs, Designs, Codes Cryp-togr. 65 (2012), 77-88.