Toughness, Trees, and Walks M. N. Ellingham1 and Xiaoya Zha2 1 DEPARTMENT OF MATHEMATICS 1326 STEVENSON CENTER VANDERBILT UNIVERSITY NASHVILLE, TN 37240 E-mail: mne@math.vanderbilt.edu 2 DEPARTMENT OF MATHEMATICAL SCIENCES MIDDLE TENNESSEE STATE UNIVERSITY MURFREESBORO, TN 37132 E-mail: xzha@mtsu.edu Received August 7, 1998; accepted July 25, 1999 Abstract: A graph is t-tough if the number of components of G\S is at most |S|/t for every cutset S ⊆ V (G). A k -walk in a graph is a spanning closed walk using each vertex at most k times. When k = 1, a 1-walk is a Hamilton cycle, and a longstanding conjecture by Chvátal is that every sufficiently tough graph has a 1-walk. When k ≥ 3, Jackson and Wormald used a result of Win to show that every sufficiently tough graph has a k -walk. We fill in the gap between k = 1 and k ≥ 3 by showing that, when k = 2, every sufficiently tough (specifically, 4-tough) graph has a 2-walk. To do this we first provide a new proof for and generalize a result by Win on the existence of a k -tree, a spanning tree with every vertex of degree at most k . We also provide new examples of tough graphs with no k -walk c 2000 John Wiley & Sons, Inc. J Graph Theory 33: 125–137, 2000 for k ≥ 2. Keywords: toughness; spanning tree; spanning walk Contract grant sponsor: NSF. Contract grant number: DMS-9622780 c 2000 John Wiley & Sons, Inc. 126 JOURNAL OF GRAPH THEORY 1. INTRODUCTION All graphs in this paper are simple and finite. The number of components of a graph G is denoted c(G). The graph G is said to be t-tough, for some nonnegative real number t, if |S| ≥ t · c(G\S) for each S ⊆ V (G) with c(G\S) ≥ 2. The toughness t(G) is the largest real number t for which G is t-tough (or +∞ if G is complete). A well-known conjecture due to Chvátal [3, Conjecture 2.3] states that all sufficiently tough graphs have a Hamilton cycle. We may generalize the idea of a Hamilton cycle to that of a k -walk: a closed spanning walk that visits every vertex of a graph at most k times. A Hamilton cycle is then a 1-walk. As we discuss below, toughness conditions for the existence of k -walks are known for k ≥ 3. Thus, for k ≥ 3 we have a known result, and for k = 1 we have a longstanding and seemingly difficult conjecture. What happens in between, for k = 2? In this paper, we show that tough enough (specifically, 4-tough) graphs do have a 2-walk. As part of our argument, we generalize and find a new proof of a result of Win [6] concerning the existence of a k -tree: a spanning tree in which every vertex has degree at most k . In the case k = 1, earlier negative results by Chvátal himself [3], Thomassen (see [2]) and Enomoto, Jackson, Katerinis and Saito [4] have recently been improved by Bauer, Broersma and Veldman [1], who showed that, for every > 0, a toughness of 94 − is not sufficient for a Hamilton path or cycle. In the case k ≥ 3, use was made of a result of Win [6] (Theorem 2.1 below), which implied that a 1/(k − 2)-tough graph has a k -tree, for k ≥ 3. Jackson and Wormald [5] observed that the existence of a k -tree implies the existence of a k walk, and thereby deduced that 1/(k − 2)-tough graphs have a k -walk for any given k ≥ 3. Win’s result had a special case guaranteeing the existence of a 2-tree, i.e., a Hamilton path, but the condition was not related to toughness. Thus, whether there were toughness conditions guaranteeing a 2-walk, 2-tree, or 1-walk all remained open. The last two questions are essentially Chvátal’s conjecture, so the question of 2-walks was left as an unresolved but probably approachable case. We solve that case in Section 4, but we require something stronger than Win’s result to do it. Win’s result may be interpreted as a condition for connecting individual vertices in a tree structure with degree restrictions; we need to connect larger subgraphs in a tree structure with degree restrictions. A generalization of Win’s result is, therefore, proved in Section 3, after we illustrate the basic idea with a new proof of Win’s original result in Section 2. Finally, in Section 5, we give some new examples of tough graphs without k -walks for k ≥ 2. 2. NEW PROOF OF WIN’S RESULT In this section, we give a new proof of Win’s result on the existence of a k -tree when k ≥ 2. The fundamental idea in Win’s proof is to take a maximal subgraph H TOUGHNESS, TREES, AND WALKS 127 having a k -tree, and try to modify the tree by adding and deleting edges, so that it is possible to add another vertex to H . However, the details are rather complicated. We present here a proof using the same fundamental idea, but shorter and more systematic. In fact, it is a special case of the proof of Theorem 3.5 in Section 3, but the essential method is less evident there due to complications needed in a more general situation. Thus, we feel it helpful to present this special case before the more general version. Recall that a bridge of a set of vertices S in a graph G is either an edge joining two vertices of S and its ends, or a component of G\S together with the edges joining it to S and their ends. Theorem 2.1 (Win [6]). Suppose that k ≥ 2 and G is a connected graph such that c(G\S) ≤ (k − 2)|S| + 2 for all S ⊆ V (G). Then G has a k -tree. Proof. Let H be an induced subgraph of G of maximum possible order having a k -tree. Suppose that H 6= G. Let A0 be the set of vertices of H that have degree k in every k -tree of H . By maximality of H , every edge from V (G)\V (H) to V (H) is incident with a vertex of A0 . Since G is connected, A0 is, therefore, nonempty. Fix some k -tree T of H . Given S ⊆ V (H), let T (S) be the set of k -trees T 0 of H such that the bridges of S in T 0 have the same vertex sets as the bridges of S in T . Suppose that T1 , T2 ∈ T (S). Let B1 be a bridge of S in T1 and B2 the corresponding bridge of S in T2 . Both B1 and B2 contain exactly one edge incident with each vertex of V (B1 ) ∩ S = V (B2 ) ∩ S . Therefore, we may replace B1 in T1 by B2 to obtain a new tree T3 ∈ T (S). Let A1 denote the set of vertices of H that have degree k in every element of T (A0 ); clearly, A0 ⊆ A1 . Suppose that there is some uv ∈ E(H) joining vertices in two different components of T \A0 . Then u and v are in different components of T 0 \A0 for any T 0 ∈ T (A0 ). Suppose that u 6∈ A1 and v 6∈ A1 . Then there are T1 , T2 ∈ T (A0 ) such that degT1 (u) < k and degT2 (v) < k . Replace the bridge of A0 in T1 containing v with the bridge of A0 in T2 containing v to obtain T3 ∈ T (A0 ), in which both u and v have degree less than k . There is at least one w ∈ A0 on the path T3 (u, v) between u and v in T3 . By adding uv to T3 and deleting one of the edges of T3 (u, v) incident with w, we obtain a k -tree of H in which w has degree less than k , contradicting w ∈ A0 . Therefore, either u ∈ A1 or v ∈ A1 or both, i.e., every edge of H joining two components of T \A0 has at least one end in A1 . Now let A2 denote the set of vertices of H that have degree k in every element of T (A1 ); clearly, A1 ⊆ A2 . Any uv ∈ E(H) joining two components of T \A1 must join two vertices within a single component of T \A0 . If neither u nor v is in A2 , then, similarly to above, we can find a tree T3 ∈ T (A1 ) in which both u and v have degree less than k , and there is a vertex w of A1 \A0 on the path T3 (u, v); but adding uv and deleting an edge of T3 (u, v) incident with w gives a tree contradicting w ∈ A1 . Thus, every edge of H joining two components of T \A1 has at least one end in A2 . 128 JOURNAL OF GRAPH THEORY We may continue in this way, in general defining Aj+1 to be the set of vertices of H with degree k in every element of T (Aj ), and deducing that every edge of H joining two components of T \Aj has both ends in Aj+1 . Thus, we have A0 ⊆ A1 ⊆ A2 ⊆ · · · ⊆ Aj ⊆ · · · ⊆ Dk (T ), where Dk (T ) is the set of vertices of degree k in T . Since Dk (T ) is finite, we must have Am = Am+1 for some m. Then we have a set Am of vertices of degree k in T such that every edge of H joining two components of T \Am has at least one end in Am , i.e., there are no such edges. Thus, we have a set S = Am of vertices of degree k in H with the property that every edge between V (H) and V (G)\V (H) has an end in S , and the vertex sets of the components of H\S and of T \S are the same. Then, as in [6], c(H\S) = c(T \S) ≥ (k − 2)|S| + 2, because T is a tree in which all elements of S have degree k . Since H 6= G, we get that c(G\S) > (k − 2)|S| + 2, a contradiction. Thus, G = H has a k -tree. 3. TOUGHNESS AND QUASITREES In this section we prove a sufficient condition, related to toughness, for the existence in a graph G of a spanning connected subgraph built by joining together the components of a given spanning subgraph F , subject to degree conditions. This result generalizes Win’s theorem (Theorem 2.1), and is used in Section 4 to prove that all 4-tough graphs have a 2-walk. We proceed by trying to join the components of F in a tree structure. The main idea is the same as in our proof of Theorem 2.1, but the details are more complicated, since we cannot delete and replace edges of F in trying to extend our tree structure, and the component counting argument varies according to the degree condition and the order of the components of F . Given a graph G, fix a (usually disconnected) spanning subgraph F . Color the edges of G as follows: edges in F or joining two vertices of the same component of F are red, and all edges joining two vertices in different components of F are green. A quasitree (derived from F ) in G is a connected subgraph of G that is the union of i components of F and i − 1 green edges whose ends lie in those components, for some i ≥ 1. Loosely, it is a subgraph of G obtained by joining some (not necessarily all) of the components of F together in a tree structure using green edges. Given k ≥ 1 and a subgraph H of G, a k -quasitree for H is a quasitree in G that is a spanning subgraph of H and in which every vertex is incident with at most k green edges. For H to have a k -quasitree, every component of F must be either disjoint from or contained in H . Our goal is a toughness-related condition for the existence of a k -quasitree for G derived from a given F . We need to modify the notions of vertex deletion, bridge, and degree to work with quasitrees. Given a subgraph H of G and a set S ⊆ V (H), let H ∼ S be the graph obtained from H by deleting all green edges incident with at least one vertex of S . Further, define a quasibridge of S in H to be either a green edge of H incident with two vertices of S and its ends, or the union of a component X of H ∼ S , all green edges of H incident with one vertex of S and one vertex of V (X)\S , and the ends TOUGHNESS, TREES, AND WALKS 129 of such green edges. Every edge of H belongs to exactly one quasibridge of S in H . Figure 1 gives an illustration of quasibridges in which we have a 2-factor as F , a set of eight vertices as S , and there are five quasibridges, two of which are single green edges. For any v ∈ V (H), the quasidegree of v in H , denoted qdegH (v), is the number of green edges of H incident with v . We need the following counting results. Lemma 3.1. Suppose that k ≥ 1, g ≥ 1, and Q is a k -quasitree derived from F, where every component of F has at least g vertices. Let S be a nonempty set of vertices of quasidegree k in Q. Then c(Q\S) ≥ (k − 2)|S| + 2 if g = 1, and (k − 1)|S| + 2 if g ≥ 2. Proof. Choose a spanning tree T of Q and pick a vertex v0 of S as the root of T . For each i ≥ 1, let pi denote the number of components of Q ∼ S containing i vertices of S , so that |S| = p1 +2p2 +3p3 +· · ·. Think of forming Q ∼ S by deleting the green edges incident with each vertex of S , processing the vertices in order of increasing distance in T from v0 . We begin by deleting the k edges incident with v0 . When we process any other vertex of S , we delete at least k − 1 edges if it is the first vertex in its component of Q ∼ S to be processed, and exactly k edges otherwise. Thus, we delete at least 1+p1 (k −1)+p2 (2k −1)+p3 (3k −1)+· · · green edges to obtain at least 2+p1 (k−1)+p2 (2k−1)+p3 (3k−1)+· · · = 2+k|S|−(p1 +p2 +· · ·) components in Q ∼ S . When we delete the vertices of S from Q ∼ S to form Q\S , we lose at most pg + pg+1 + pg+2 + · · · components, so that c(Q\S) ≥ 2 + k|S| − ((p1 + p2 + · · · + pg−1 ) + 2(pg + pg+1 + · · ·)). FIGURE 1. An illustration of quasibridges. 130 JOURNAL OF GRAPH THEORY Now (p1 + p2 + · · · + pg−1 ) + 2(pg + pg+1 + · · ·) ≤ 2|S| if g = 1, or |S| if g ≥ 2, giving the desired result. This result is sharp. Take a tree T in which every vertex has degree either k or 1, and let S be the set of vertices of degree k in T . Take a collection of |V (T )| disjoint complete graphs Kg , and identify one vertex of each Kg with a distinct vertex of T to form Q; let F be the union of all the Kg ’s. Then c(Q\S) is exactly the stated number. An example with k = 3 and g = 4 is shown in Fig. 2. Unfortunately, Lemma 3.1 does not provide very useful information in the case where k = 1. We therefore use a corollary to the following lemma. Lemma 3.2. Suppose that Q is a quasitree, and let R be a nonempty set of green edges of Q. Then, for any q ≥ 2, the number of components of Q\R incident in Q with fewer than q edges of R is at least (q − 2)|R|/(q − 1) + q/(q − 1). Proof. Let r = |R|. For each i, let ni be the number of components of Q\R incident with exactly i edges of R. Since Q is a quasitree, Q\R has r + 1 components. Standard counting arguments give n1 + n2 + n3 + · · · = r + 1 (1) n1 + 2n2 + 3n3 + · · · = 2r, (2) and from q(1) − (2) we get (q − 1)n1 + (q − 2)n2 + · · · + nq−1 − nq+1 − 2nq+2 · · · = (q − 2)r + q. FIGURE 2. Sharpness of Lemma 3.1. TOUGHNESS, TREES, AND WALKS 131 Hence, n1 + n2 + · · · + nq−1 ≥ (q − 1)n1 + (q − 2)n2 + · · · + nq−1 (q − 2)r + q ≥ . q−1 q−1 Corollary 3.3. Suppose that g ≥ 2 and Q is a 1-quasitree derived from F, where every component of F has at least g vertices. Let S be a nonempty set of vertices of quasidegree 1 in Q. Then c(Q\S) ≥ g−2 g |S| + . 2(g − 1) g−1 Proof. In forming Q ∼ S , we delete a set R of at least |S|/2 green edges, and any component of Q ∼ S = Q\R with less than q = g deleted green edges incident with it gives rise to a component of Q\S . The result then follows from Lemma 3.2. Both Lemma 3.2 and Corollary 3.3 are sharp: Let T be any tree, all of whose vertices have either degree g or 1. Obtain a quasitree Q from T by replacing each vertex of T by a copy of Kg , the edges of T becoming a matching in Q, and F consisting of all the Kg ’s. If we take R to be the set of all the green edges and q = g , then c(Q\R) meets the bound of Lemma 3.2, and, if we take S to be the set of all the vertices of quasidegree 1, i.e., the ends of all the green edges, then c(Q\S) meets the bound of Corollary 3.3. An example with g = 3 is shown in Fig. 3. It is possible to generalize Corollary 3.3 to k -quasitrees for any k , but for k ≥ 2 this never yields a better result than Lemma 3.1. Observation 3.4. Note that, if the quasitree Q is a spanning subgraph of a graph H , and the components of Q ∼ S and H ∼ S have the same vertex sets, then the lower bound of Lemma 3.1 or Corollary 3.3 also applies to c(H\S). FIGURE 3. Sharpness of Lemma 3.2 and Corollary 3.3. 132 JOURNAL OF GRAPH THEORY We now state our generalization of Win’s theorem (Theorem 2.1). Win’s theorem is just the case of our result in which k ≥ 2 and F is the spanning subgraph of G with no edges, so that g = 1. For our result on 2-walks, we just need the case k = 1, but only a little extra effort (Lemma 3.1) is required to handle k ≥ 2 as well. Theorem 3.5. Suppose that g and k are positive integers with g+k ≥ 3. Suppose further that G is a connected graph with a spanning subgraph F, each component of which has order at least g, and that for every S ⊆ V (G) we have c(G\S) < g−2 2(g−1) |S| + 2g−1 g−1 if k = 1 and g ≥ 2, or (k − 2)|S| + 3 if k ≥ 2 and g = 1, or (k − 1)|S| + 3 if k ≥ 2 and g ≥ 2. Then G has a k -quasitree derived from F, i.e., a connected spanning subgraph consisting of F and c(F ) − 1 other edges, with every vertex being incident with at most k of the other edges. Proof. Fix F . Let H be an induced subgraph of G of maximum possible order for which there is a k -quasitree. Suppose that H 6= G. Let A0 be the set of vertices of H that have quasidegree k in every k -quasitree for H . By maximality of H , every edge from V (G)\V (H) to V (H) is incident with a vertex of A0 . Since G is connected, A0 is therefore nonempty. Fix some k -quasitree Q for H . Given S ⊆ V (H), let Q(S) be the set of k quasitrees Q0 for H such that the quasibridges of S in Q0 have the same vertex sets as the quasibridges of S in Q. Suppose that Q1 , Q2 ∈ Q(S). Let B1 be a quasibridge of S in Q1 and B2 the corresponding quasibridge of S in Q2 . At each vertex v of V (B1 ) ∩ S = V (B2 ) ∩ S , either both B1 and B2 contain the component F (v) of F that includes v , or both contain no edges of F (v). In the former case, B1 and B2 both include, of the edges incident with v , all red edges and no green ones, and, in the latter case, both include, of the edges incident with v , no red edges and exactly one green one. Therefore, we may replace B1 in Q1 by B2 to obtain a new quasitree Q3 ∈ Q(S). Let A1 denote the set of vertices of H that have quasidegree k in every element of Q(A0 ); clearly, A0 ⊆ A1 . Suppose that there is some uv ∈ E(H ∼ A0 ) joining vertices in two different components of Q ∼ A0 . Since all red edges have both ends in the same component of F and hence the same component of Q ∼ A0 , uv is green, and since uv ∈ E(H ∼ A0 ), neither u nor v is in A0 . Also, u and v are in different components of Q0 ∼ A0 for any Q0 ∈ Q(A0 ). Suppose that u 6∈ A1 and v 6∈ A1 . Then there are Q1 , Q2 ∈ Q(A0 ) such that qdegQ1 (u) < k and qdegQ2 (v) < k . Replace the quasibridge of A0 in Q1 containing v with the quasibridge of A0 in Q2 containing v to obtain Q3 ∈ Q(A0 ), in which both u and v have quasidegree less than k . There is at least one green edge wx, with w ∈ A0 , that separates u from v in Q3 . By adding uv to Q3 and deleting wx, we obtain a k -quasitree for H in which w has quasidegree less than k , contradicting w ∈ A0 . Therefore, either u ∈ A1 or TOUGHNESS, TREES, AND WALKS 133 v ∈ A1 or both, i.e., every edge of H ∼ A0 joining two components of Q ∼ A0 has at least one end in A1 . Now let A2 denote the set of vertices of H that have quasidegree k in every element of Q(A1 ); clearly, A1 ⊆ A2 . Any uv ∈ E(H ∼ A1 ) joining two components of Q ∼ A1 must be green, must join vertices within a single component of Q ∼ A0 , and neither u nor v can be in A1 . If neither u nor v is in A2 , then, similarly to above, we can find a quasitree Q3 ∈ Q(A1 ) in which both u and v have quasidegree less than k , and there is a green edge wx, with w ∈ A1 \A0 , separating u from v in Q3 ; but adding uv and deleting wx gives a quasitree contradicting w ∈ A1 . Thus, every edge of H ∼ A1 joining two components of Q ∼ A1 has at least one end in A2 . We may continue in this way, in general defining Aj+1 to be the set of vertices of H with quasidegree k in every element of Q(Aj ), and deducing that every edge of H ∼ Aj joining two components of Q ∼ Aj has both ends in Aj+1 . Thus, we have A0 ⊆ A1 ⊆ A2 ⊆ · · · ⊆ Aj ⊆ · · · ⊆ Dk (Q), where Dk (Q) is the set of vertices of quasidegree k in Q. Since Dk (Q) is finite, we must have Am = Am+1 for some m. Then we have a set S = Am of vertices of quasidegree k in Q such that every edge uv of H ∼ S = H ∼ Am joining two components of Q ∼ S = Q ∼ Am has at least one end in S = Am+1 . Note that any such uv must be green, because all red edges of H join two vertices in the same component of Q ∼ S . But then uv cannot be an edge of H ∼ S . Thus, there are no edges of H ∼ S joining two components of Q ∼ S , so that the vertex sets of the components of Q ∼ S and H ∼ S are the same. Now we may obtain a lower bound on c(H\S) using Observation 3.4 and either Lemma 3.1 or Corollary 3.3. Since H 6= G, c(G\S) ≥ c(H\S) + 1, which contradicts the bound on c(G\S) in the hypothesis of the theorem. Thus, G = H has a k -quasitree derived from F . Note that in applying Theorem 3.5, we may add edges to G so that every component of F becomes a complete graph. This has no effect on the existence of a k -quasitree, and may make it easier to satisfy the inequality required by the theorem. 4. TOUGHNESS AND 2-WALKS In this section we apply the main result of Section 3 to show that all 4-tough graphs have a 2-walk. We use a 1-quasitree derived from a 2-factor to establish the existence of a 2-walk. Theorem 4.1. Suppose that G is a graph, where c(G\S) ≤ min{|S|/2, (|S| + 9)/4} for every subset S ⊆ V (G) with c(G\S) ≥ 2. (In particular, it suffices if G is 4-tough.) Then G has a 2-walk. Proof. The given condition implies that G is 2-tough and hence connected; moreover, since Enomoto, Jackson, Katerinis, and Saito [4] proved that every k -tough graph has a k -factor, G has a 2-factor F . Now, since c(G\S) ≤ (|S| 134 JOURNAL OF GRAPH THEORY + 9)/4 < |S|/4 + 5/2, it follows from Theorem 3.5 with g = 3 and k = 1 that G has a 1-quasitree Q derived from F . Replacing each green edge of Q by two parallel edges creates an Eulerian multigraph in which each vertex has degree 2 or 4, and a closed Eulerian trail in this multigraph corresponds to a 2-walk in Q and hence in G. If we know that G has a 2-factor in which every component is of length at least g , where g ≥ 4, then we can improve our argument in an obvious way. Theorem 4.2. Suppose that G is a connected graph with a 2-factor F in which every component has length at least g, g ≥ 3. Suppose further that 4g − 3 |S| (g − 2) , |S| + c(G\S) ≤ min 2 2(g − 1) 2(g − 1) for all S ⊆ V (G) with c(G\S) ≥ 2. (In particular, it suffices if G has girth at least g and is (2 + 2/(g − 2))-tough.) Then G has a 1-quasitree derived from F, and, hence, a 2-walk. 5. GRAPHS WITHOUT K -WALKS In this final section, we discuss the maximum toughness of a graph without a k -walk, by means of some examples. The toughest previous examples of graphs with no k -walk were given by Jackson and Wormald [5]. Unfortunately, the toughness they stated for their examples was incorrect. We briefly describe their examples and give the correct toughness. Given k ≥ 1, take K3 , and attach k pendant vertices to each of the three vertices to obtain a graph H . Let G = Gk,s = (mH) + Ks , where m = d(sk + 1)/2e and s is arbitrary (mH means m disjoint copies of H , and + denotes join). This graph G has no k -walk, because any k -walk would have to enter and leave each copy of H twice, but m is too large relative to s for this. Jackson and Wormald claimed that t(G) approaches f1 (k) = 1/k + 2/(3k 2 ) as s → ∞. In fact, t(G) = f2 (k, s) = (s + 2m)/(m(2k + 1)), which approaches f2 (k) = 2(k + 1)/(k(2k + 1)). The correct asymptotic toughness f2 (k) is always less than the claimed f1 (k). It is easy to show that t(G) ≤ f2 (k, s): delete two vertices of the K3 in each copy of H and all vertices of the Ks . More work, which we omit, can show that t(G) = f2 (k, s). We now show that the recent construction by Bauer, Broersma, and Veldman (BBV) [1] of graphs with no 1-walk and toughness approaching 94 can be generalized to yield graphs with no k -walk and toughness approaching g(k) = (8k + 1)/(4k(2k − 1)), for every k ≥ 1. This is better than the Jackson and Wormald examples. The BBV construction starts from a graph H with a distinguished edge uv . First, form Fm by taking m disjoint copies H1 , H2 , . . . , Hm of H , with ui vi in Hi corresponding to uv in H , and then adding edges to make a complete graph on {u1 , v1 , . . . , um , vm }. Now let G = G(H, uv, l, m) = Fm + Kl . As stated in [1], if H has no Hamilton cycle through uv and if m ≥ 2l + 1, then G has no Hamilton TOUGHNESS, TREES, AND WALKS 135 cycle. We observe more generally that if H has no k -walk using uv at least once and if m ≥ 2kl + 1, then G has no k -walk. The difficulty in the BBV construction comes in finding a suitable graph H and edge uv so that the toughness of G is large, and provably so. BBV use the graph H = L1 shown in Fig. 4 with the edge uv as indicated. For k > 1, we obtain Lk by attaching k − 1 pendant vertices to each of the six vertices of L1 with degree 3 or 4. It is not difficult to see that Lk has no k -walk using uv , and so we may use the BBV construction starting from Lk and uv to get G with no k -walk. We need to determine the toughness of the resulting G. The reasoning required is more complicated than in the case k = 1. We give it in full, because toughness is not an easy quantity to verify. Proposition 5.1. For k ≥ 1, l ≥ 2, and m ≥ 2kl + 1, the graph G = G(Lk , uv, l, m) has no k -walk and toughness t(G) = l + 4m . 1 + 2m(2k − 1) Proof. From our discussion above, G has no k -walk. Suppose that S is a cutset of G that attains the toughness, i.e., t(G) = |S|/c(G \ S). S must contain all vertices of the Kl . Moreover, in each copy Hi of H = Lk , the set S contains none of the 6(k − 1) vertices of degree 1 or the two vertices of degree 2, as such vertices increase |S| while decreasing c(G \S). Let Si = S ∩ V (Hi ) and si = |Si | ≤ 6 for each i. Moreover, let wi denote the number of components of Hi \Si that do not contain either ui or vi . Then P l+ m si |S| P i=1 , = t(G) = c(G \S) e+ m w i=1 i where e = 0 if {u1 , v1 , . . . , um , vm } ⊆ S , and 1 otherwise. For each i, it is not difficult to establish the following tight upper bound b(si ) on wi : s 0 1 2 3 4 5 6 . b(s) 0 k − 1 2k − 1 3k − 2 4k − 2 5k − 3 6k − 4 FIGURE 4. L1 . 136 JOURNAL OF GRAPH THEORY It is easier to work with the reciprocal of t(G) for a while. Let nj = |{i : si = j}| for 0 ≤ j ≤ 6, then n0 + n1 + · · · + n6 = m, and P e+ m 1 wi Pi=1 = m t(G) l + i=1 si 1 + b(0)n0 + b(1)n1 + b(2)n2 + b(3)n3 + b(4)n4 + b(5)n5 + b(6)n6 ≤ l + 0n0 + 1n1 + 2n2 + 3n3 + 4n4 + 5n5 + 6n6 1 + (k − 1)n1 + (2k − 1)n2 + (3k − 2)n3 + (4k − 2)n4 + (5k − 3)n5 + (6k − 4)n6 = l + n1 + 2n2 + 3n3 + 4n4 + 5n5 + 6n6 1 + n2 + n3 + 2n4 + 2n5 + 2n6 − (k − 1)l = k−1+ . l + n1 + 2n2 + 3n3 + 4n4 + 5n5 + 6n6 Let us try to maximize this expression over all nonzero integers n0 , n1 , . . . , n6 summing to m. For a maximum expression, the numerator of the fraction must be positive, as we can make it positive by choosing, say, n2 = m > (k − 1)l and all other nj equal to 0. Clearly n1 = 0, otherwise we could let n00 = n0 + n1 and n01 = 0, increasing the expression. By similar arguments, n3 = 0 and n5 = n6 = 0. So now we must choose n0 , n2 , n4 to maximize the expression k−1+ 1 + n2 + 2n4 − (k − 1)l 1 1 − (k − 1/2)l =k− + . l + 2n2 + 4n4 2 l + 2n2 + 4n4 Because the numerator on the right is negative, the expression is maximized when 2n2 + 4n4 is maximized, i.e., when n0 = n2 = 0 and n4 = m. Thus, 1 1 1 − (k − 1/2)l 1 + 2m(2k − 1) ≤k− + = , t(G) 2 l + 4m l + 4m and hence t(G) ≥ (l + 4m)/(1 + 2m(2k − 1)). On the other hand, we see immediately that t(G) ≤ (l + 4m)/(1 + 2m(2k − 1)) by considering the cutset consisting of V (Kl ) and the four vertices of degree 4 in each copy of L1 ⊆ Lk = H . Thus, G has the claimed toughness. If we take m = 2kl + 1 and l → ∞, we have a family of graphs with no k -walk and asymptotic toughness g(k) = (8k + 1)/(4k(2k − 1)). To compare this with Jackson and Wormald’s examples, it is convenient to look at the reciprocals of the asymptotic toughness: 1 1 k(2k + 1) 1 vs. = =k− + f2 (k) 2(k + 1) 2 2(k + 1) 4k(2k − 1) 5 5 1 = =k− + . g(k) 8k + 1 8 8(8k + 1) This shows that our examples are significantly closer to the upper bound on the toughness of graphs without k -walks proposed by the following conjecture. Conjecture (Jackson and Wormald, [5]). graph has a k -walk. For k ≥ 2, every (1/(k − 1))-tough TOUGHNESS, TREES, AND WALKS 137 For k = 2, our examples without 2-walks have toughness approaching 17/24. Comparing this to our result that a 4-tough graph has a 2-walk, we see that there is a large gap to be closed. Thus, while this paper demonstrates that there is a toughness sufficient to guarantee a 2-walk, our result is almost certainly not sharp. For k ≥ 3, there is also a gap between our examples without k -walks and the result of Jackson and Wormald that a 1/(k − 2)-tough graph has a k -walk. For k = 1, Chvátal’s conjecture is still completely open. Therefore, there is much still to be resolved regarding the close connection between toughness and the existence of k -walks. References [1] D. Bauer, H. J. Broersma, and H. J. Veldman, Not every 2-tough graph is hamiltonian, preprint (1997). [2] J.-C. Bermond, ‘‘Hamiltonian graphs,’’ Selected topics in graph theory, L. W. Beineke and R. J. Wilson (Editors), Academic Press, London, 1978, pp. 127–167. [3] V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Math 5 (1973), 215–228. [4] H. Enomoto, B. Jackson, P. Katerinis, and A. Saito, Toughness and the existence of k -factors, J Graph Theory 9 (1985), 87–95. [5] B. Jackson and N. C. Wormald, k -walks of graphs, Australas J Combin 2 (1990), 135–146. [6] S. Win, On a connection between the existence of k -trees and the toughness of a graph, Graphs Combin 5 (1989), 201–205.

1/--страниц