More than One Tough Chordal Planar Graphs are Hamiltonian Thomas Böhme,1 Jochen Harant,1 and Michal Tkáč2 1 DEPARTMENT OF MATHEMATICS ILMENAU TECHNICAL UNIVERSITY D-98684 ILMENAU, PF 100 565, GERMANY 2 DEPARTMENT OF MATHEMATICS TECHNICAL UNIVERSITY OF KOŠICE 042 00 KOŠICE, SLOVAKIA 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 1. INTRODUCTION AND NOTATION 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. c 1999 John Wiley & Sons, Inc. CCC 0364-9024/99/040405-06 406 JOURNAL OF GRAPH THEORY Conjecture (Chvátal [4]). There is a t0 > 0 such that every t0 -tough graph is Hamiltonian. 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 by τ (Γ) = lim inf G∈Γ 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. TOUGH CHORDAL PLANAR GRAPHS ARE HAMILTONIAN 407 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 by ∗ fn−4 (xn xn−1 xn−3 xn ) = xn xn−1 408 JOURNAL OF GRAPH THEORY ∗ fn−4 (xn−1 xn−2 xn−3 xn−1 ) = xn−2 xn−3 ∗ fn−4 (xn xn−1 xn−2 xn ) = xn−1 xn−2 ∗ fn−4 (xn xn−2 xn−3 xn ) = xn xn−3 . ∗ fn−4 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. TOUGH CHORDAL PLANAR GRAPHS ARE HAMILTONIAN 409 (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 lim where c(Gn ) is the length of a longest cycle of Gn . This completes the proof of (1.2). 410 JOURNAL OF GRAPH THEORY References [1] D. Bauer, H. J. Broersma, and H. J. Veldman, Not every 2-tough graph is Hamiltonian, preprint, Memorandum No. 1400, Universiteit Twente, July 1997. [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. 127–167. [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), 215–228. [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), 71–76. [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), 99–116.

1/--страниц