close

Вход

Забыли?

вход по аккаунту

?

503

код для вставкиСкачать
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.
Документ
Категория
Без категории
Просмотров
7
Размер файла
167 Кб
Теги
503
1/--страниц
Пожаловаться на содержимое документа