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



код для вставкиСкачать
More than One Tough
Chordal Planar Graphs are
Thomas Böhme,1 Jochen Harant,1 and Michal Tkáč2
D-98684 ILMENAU, PF 100 565, GERMANY
Abstract: We prove the result stated in the title. Furthermore, it is proved that
for any > 0, there is a 1-tough chordal planar graph G such that the length of a
c 1999 John Wiley & Sons, Inc. J Graph Theory 32:
longest cycle of G is less than |V (G )|. 405–410, 1999
Keywords: Hamiltonian cycles; chordal planar graphs; toughness
Let G be a connected graph. A subset S of V (G) separates G, if the graph G − S
obtained from G by deleting the vertices of S is disconnected. G is said to be k tough, if for every separating set S ⊆ V (G) the number ω(G − S) of components
of G−S is at most |S|/k . The toughness τ (G) of a noncomplete graph G is defined
to be the largest integer t > 0 such that G is t-tough. For a complete graph G, we
let τ (G) = ∞. The concept of toughness was introduced by Chvátal [4] in 1973.
It is easy to see that every Hamiltonian graph is 1-tough. In [4], Chvátal made the
following conjecture.
1999 John Wiley & Sons, Inc.
CCC 0364-9024/99/040405-06
Conjecture (Chvátal [4]). There is a t0 > 0 such that every t0 -tough graph is
In [4], the stronger conjecture was also made that every 32 -tough graph is Hamiltonian. This conjecture was first disproved by Thomassen (see [2]). Enomoto, Jackson, Katerinis, and Saito [7] showed that every 2-tough graph has a 2-factor (a
2-regular spanning subgraph), while for every > 0 there is a (2 − )-tough graph
without a 2-factor.
For a long time it was conjectured that every 2-tough graph is Hamiltonian.
This conjecture remained open until Bauer, Broersma, and Veldman [1] recently
disproved it by constructing a ( 94 − )-tough non-Hamiltonian graph for arbitrary
> 0.
More is known about the existence of Hamiltonian cycles in planar and chordal
graphs. It follows from a well-known theorem of Tutte [13] that, for t > 32 , every
t-tough planar graph is Hamiltonian. Furthermore, in [9] it was proved that for every
> 0 there is a 54 -tough maximal planar graph G such that the length of a longest
cycle of G is less than |V (G)|. Recently, Owens [10] constructed ( 32 − )-tough
maximal planar non-Hamiltonian graphs for arbitrary > 0. A graph G is chordal,
if it does not contain an induced cycle on at least four vertices. Chen, Jacobson,
Kézdy, and Lehel [3] proved that every 18-tough chordal graph is Hamiltonian. In
[1] it is shown that for every > 0 there exists a ( 74 − )-tough non-Hamiltonian
chordal graph.
In the present article the following two results are proved.
(1.1) Every chordal planar graph with toughness greater than one is Hamiltonian.
(1.2) The shortness exponent of the class of all 1-tough chordal planar graphs is at
most log 8/ log 9.
According to [8], the shortness exponent τ (Γ) of a class Γ of graphs is defined
τ (Γ) = lim inf
log c(G)
log |V (G)|
where c(G) denotes the length of a longest cycle in G.
It is not hard to see that if τ (Γ) < 1, then there is a sequence G1 , G2 , · · · of graphs
in Γ such that c(Gi )/|V (Gi )| → 0 as i → ∞. Thus, (1.2) implies the second result
stated in the abstract.
2. PROOF OF (1.1)
Before proceeding with the proof of (1.1), several results about chordal and planar
graphs are given.
A vertex x of a graph G is called a simplicial vertex of G, if the subgraph of
G induced by the neighbors of x is complete. The following proposition is due to
Dirac [6].
(2.1) (Dirac [6]) Every chordal graph has a simplicial vertex.
An ordering x1 x2 · · · xn of the vertex set of a graph G is a perfect elimination order, if x1 is a simplicial vertex of G and xi is a simplicial vertex of
G − {x1 , . . . , xi−1 } for i = 2, . . . , n. The easy proof of the following proposition
is left to the reader.
(2.2) A graph is chordal if and only if it has a perfect elimination order.
(2.3) Let G be an l-connected chordal graph, x1 x2 · · · xn be a perfect elimination
order of G, and i ∈ {1, . . . , n − 1}. Then the graph G − {x1 , . . . , xi } is either
l-connected or complete.
Proof. Suppose that there is a counterexample G. Then there is a smallest i ∈
{1, . . . , n−1} such that H = G−{x1 , . . . , xi } is neither l-connected nor complete.
Thus, there is a separating set S ⊆ V (H) of H such that |S| ≤ l − 1. Let H1
and H2 be two components of H − S . By minimality of i, S does not separate
G − {x1 , . . . , xi−1 }. Consequently, xi is adjacent to a vertex y1 ∈ V (H1 )\S
and to a vertex y2 ∈ V (H2 )\S in G. Since xi is a simplicial vertex of G −
{x1 , . . . , xi−1 }, y1 y2 ∈ E(H)—a contradiction.
(2.4) Let G be a 3-connected planar graph, H be a 3-connected subgraph of G, and
D be a 3-cycle that separates H . Then
(a) H − V (D) has exactly two components, and
(b) D separates G.
Proof. Let D = (a, b, c, a), H1 , H2 , . . . , Hr with r ≥ 2 be the components of
H − V (D), and yi ∈ V (Hi )\V (D) for i ∈ {1, . . . , r}. It follows from Menger’s
theorem that, for each i ∈ {1, . . . , r}, there are three (yi , V (D))-paths P1i , P2i , P3i
of Hi such that V (Pji ) ∩ V (Pki ) = {yi } for 1 ≤ j < k ≤ 3. Since H is planar,
it contains no K3,3 -minor and, consequently, r ≤ 2. This proves (a). To prove (b),
suppose that there is a (y1 , y2 )-path Q of G such that V (Q) ∩ V (D) = ∅. Then it is
not hard to see that the subgraph of G formed by D, P11 , P21 , P31 , P12 , P22 , P32 , and
Q contains a K5 -minor—a contradiction.
Now we are ready for the proof of (1.1). Let G be a chordal planar graph with
toughness greater than one. Since G is more than 1-tough, it is also 3-connected. Let
x1 x2 · · · xn be a perfect elemination order of G, and for 1 ≤ i ≤ n−1 let Hi denote
the graph G−{x1 , . . . , xi }. Since the degree of a simplicial vertex of a planar graph
cannot be greater than three, and since G is 3-connected, it follows from (2.3) that
for 1 ≤ i ≤ n − 3 the subgraph Di of Hi−1 induced by the neighbors of xi is a
3-cycle. We call a 3-cycle D of Hi an active 3-cycle of Hi , if D is separating in G
and nonseparating in Hi . An extendable pair of Hi is an ordered pair (C, f ), where
C is a Hamiltonian cycle of Hi and f is an injection that maps every active 3-cycle
D of Hi onto an edge f (D) such that f (D) ∈ E(C ∩ D). We claim that for every
i = 1, . . . , n−4, there is an extendable pair (Ci , fi ) of Hi . The proof is by induction
on k = n − i. If k = 4, then it follows from (2.3) that Hn−4 is a complete graph
with the vertex set {xn , xn−1 , xn−2 , xn−3 }. Let Cn−4 = (xn xn−1 xn−2 xn−3 xn ),
and define fn−4
(xn xn−1 xn−3 xn ) = xn xn−1
(xn−1 xn−2 xn−3 xn−1 ) = xn−2 xn−3
(xn xn−1 xn−2 xn ) = xn−1 xn−2
(xn xn−2 xn−3 xn ) = xn xn−3 .
is a bijection between the set of all 3-cycles of Hn−4 and the edge set of Cn−4 .
Thus, if C is the set of all active 3-cycles of Hn−4 , the pair (Cn−4 , fn−4 ), where
fn−4 denotes the restriction of fn−4
to C is an extendable pair of Hn−4 .
We proceed with the inductive step. Let k = n−i ≥ 5. Since Hi is a planar graph
with at least five vertices, Hi is not complete and, consequently, it follows from
(2.3) that Hi is 3-connected. We claim that Di is an active 3-cycle of Hi . To prove
this, consider the graph Hi−1 − V (Di ). Since the neighborhood of xi in Hi−1 is
V (Di ), it follows that Hi−1 − V (Di ) is disconnected and that the vertex set of one
of the components consists of xi only. By (2.4)(b), Di separates G, and by (2.4)(a),
Hi−1 − V (Di ) has precisely two components, F1 = Hi−1 − (V (Di ) ∪ {xi }) =
Hi − V (Di ) and F2 = xi . It follows that Hi − V (Di ) is connected. Consequently,
Di is an active cycle of Hi .
By the inductive hypothesis there is an extendable pair (Ci , fi ) of Hi . Let
V (Di ) = {a, b, c} and fi (Di ) = ab. Since Di is separating in Hi−1 , Di is not
an active cycle of Hi−1 . There are precisely three new 3-cycles in Hi−1 , Ca =
(xi bcxi ), Cb = (xi caxi ), and Cc = (xi abxi ). We claim that at most two of them
are active 3-cycles of Hi−1 . To prove this, we suppose that all of them are separating
in G. Let z ∈ {a, b, c}. By (2.4)(a), G − V (Cz ) has precisely two components.
Let Gz denote the component of G − V (Cz ) that does not contain z , and let Gx
be the component of G − V (Di ) that does not contain xi . It is not hard to see that
Ga , Gb , Gc , and Gx are pairwise disjoint. Consequently, G−{a, b, c, xi } has at least
four components, contradicting the fact that G is more than 1-tough. This proves
that at most two of the 3-cycles Ca = (xi bcxi ), Cb = (xi caxi ), and Cc = (xi abxi )
are active 3-cycles of Hi−1 . Thus, we may assume that Cc is not an active 3-cycle
of Hi−1 .
Let Ci−1 be the Hamiltonian cycle of Hi−1 obtained from Ci by replacing the
edge ab by the path (axi b), and define fi−1 as follows. Let D̃ be an active 3-cycle of
Hi−1 . If D̃ ⊆ Hi , it follows from (2.4)(b) that D̃ is an active 3-cycle of Hi , and we
let fi−1 (D̃) = fi (D̃). For z ∈ {a, b} and z 0 ∈ {a, b}\{z}, we let fi−1 (Cz ) = xi z 0
if Cz is an active 3-cycle of Hi−1 . Now it is easy to see that (Ci−1 , fi−1 ) is an
extendable pair of Hi−1 . This proves (1.1).
3. PROOF OF (1.2)
We use the concept of W -supertoughness introduced in [5] as follows.
Let G be a 1-tough graph, and let W ⊂ V (G). G is W -supertough, if ω(G−S) ≤
|S| − 1 for any separating set S with W ⊆ S ⊂ V (G).
In [11] the following proposition is proved. It will be used to establish (3.2) below.
(3.1) Let G be a graph on the vertex set V (G) and let S ⊆ V (G). If G − v is
1-tough for a vertex v ∈ V (G), and if ω(G − S) > |S|, then v does not belong to
S but all its neighbors do.
Let H be a complete graph on four vertices {x, y, z, u}, and let T (x, y, z) be
the graph obtained from H by adding three new vertices vx , vy , vz such that for
a ∈ {x, y, z} the neighborhood of va is {x, y, z, u}\{a}. It is easy to see, that
T (x, y, z) is a planar graph, and that every (x, y)-path of T (x, y, z) not containing
z omits at least one of the vertices vx , vy , vz . Let H1 denote the graph obtained from
three copies T (x1 , y1 , z1 ), T (x2 , y2 , z2 ), T (x3 , y3 , z3 ) of T (x, y, z) by identifying
the vertices z1 , z2 , and z3 and adding the edges y1 x2 , y2 x3 , y3 x1 , x1 x2 , x2 x3 , x3 x1 .
The graph H1 contains precisely nine vertices of degree three. Each of them is a
simplicial vertex of H1 , and these are the only simplicial vertices of H1 .
(3.2) (a) Every cycle of H1 omits at least one simplicial vertex.
(b) H1 is {x1 , x2 , x3 }-supertough.
Proof. (a) Let C be a cycle of H1 . If C contains all simplicial vertices of H1 ,
then there is an index j ∈ {1, 2, 3} such that the intersection of C and T (xj , yj , zj )
is an (xj , yj )-path that does not contain zj —a contradiction.
(b) We first prove that H1 is 1-tough. Suppose that there is a separating set S ⊆
V (H1 ) such that |S| < ω(H1 − S). An easy case analysis shows that deleting an
arbitrary simplicial vertex from H1 results in a Hamiltonian graph. Consequently,
it follows from (3.1) that S consists of all vertices of H1 with degree greater than
three. Thus, |S| = 10 and ω(H1 − S) = 9—a contradiction. To see that H1 is
{x1 , x2 , x3 }-supertough, it suffices to show that the graph H ∗ obtained from H1
by adding a new vertex x and three edges xx1 , xx2 , xx3 is 1-tough. The graph H ∗
has ten simplicial and ten nonsimplicial vertices, and it becomes Hamiltonian after
removing any simplicial vertex. The result follows by (3.1).
Now we define a sequence of graphs {Hn } as follows. For n ≥ 2, let Hn be
the graph obtained from Hn−1 by deleting each simplicial 3-valent vertex v of
Hn−1 and replacing it with a copy of H1 in the following way: If v1 , v2 , and v3 are
the neighbors of v in Hn−1 , delete v and insert a copy of H1 and add the six new
edges x1 v1 , x1 v2 , x1 v3 , x2 v2 , x2 v3 , and x3 v3 . Since H1 is {x1 , x2 , x3 }-supertough,
it follows from Lemma 1 in [9] that each Hn is 1-tough. Moreover, an easy induction
on n using (2.2) shows that each Hn is chordal and planar.
For every n, Hn contains 9n simplicial 3-valent vertices and at most 8n of them
can lie on a cycle through Hn . Reasoning similar to that in [5, 9, 12] leads to the
following equation:
log 8
log c(Gn )
n→∞ log |V (Gn )|
log 9
where c(Gn ) is the length of a longest cycle of Gn . This completes the proof
of (1.2).
[1] D. Bauer, H. J. Broersma, and H. J. Veldman, Not every 2-tough graph is
Hamiltonian, preprint, Memorandum No. 1400, Universiteit Twente, July
[2] J. C. Bermond, ‘‘Hamiltonian graphs,’’ L. Beinecke and R. J. Wilson, eds.,
Selected topics in graph theory, Academic, London and New York, 1978, pp.
[3] G. Chen, M. S. Jacobson, A. Kézdy, and J. Lehel, Tough enough chordal
graphs are Hamiltonian, preprint.
[4] V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Math 5 (1973),
[5] M. B. Dillencourt, An upper bound on the shortness exponent of 1-tough,
maximal planar graphs, Discrete Math 90 (1991), 93–97.
[6] G. A. Dirac, On rigid circuit graphs, Abh Math Sem Univ Hamburg 25 (1961),
[7] H. Enomoto, B. Jackson, P. Katarinis, and A. Saito, Toughness and the existence of k -factors, J Graph Theory 9 (1985), 87–95.
[8] B. Grünbaum and H. Walther, Shortness exponents of families of graphs, J
Combin Theory 14 (1973), 364–385.
[9] J. Harant and P. J. Owens, Non-hamiltonian 54 -tough maximal planar graphs,
Discrete Math 147 (1995), 301–305.
[10] P. Owens, Non-Hamiltonian maximal planar graphs with high toughness,
preprint, Univ Surrey, 1988.
[11] T. Nishizeki, A 1-tough nonhamiltonian maximal planar graph, Discrete Math
30 (1980), 305–307.
[12] M. Tkáč, On the shortness exponent of 1-tough, maximal planar graphs,
Discrete Math 154 (1996), 321–328.
[13] W. T. Tutte, A theorem on planar graphs, Trans Amer Math Soc 82 (1956),
Без категории
Размер файла
176 Кб
Пожаловаться на содержимое документа