Discussiones
Mathematicae Graph Theory 22(1) (2002) 193-198
DOI: https://doi.org/10.7151/dmgt.1168
TRESTLES IN POLYHEDRAL GRAPHS
Michal Tkáč
Department of Mathematics |
Heinz-Jürgen Voss
Institute of Algebra |
Abstract
A k-trestle of a graph G is a 2-connected spanning subgraph of G of maximum degree at most k. We show that a polyhedral graph G has a 3-trestle, if the separator-hypergraph of G contains no two different cycles joined by a path of 3-separators of length ≥ 0. There are graphs not satisfying this condition that have no 3-trestles. Further, for each integer k every graph with toughness smaller than [2/k] has no k-trestle.Keywords: polyhedral graphs, non-Hamiltonian, k-trestle.
2000 Mathematics Subject Classification: Primary 05C38, Secondary 52B10.
References
[1] | D. Barnette, 2-connected spanning subgraphs of planar 3-connected graphs, J. Combin. Theory (B) 61 (1994) 210-216, doi: 10.1006/jctb.1994.1045. |
[2] | T. Böhme and J. Harant, On hamiltonian cycles in 4- and 5-connected planar triangulations, Discrete Math. 191 (1998) 25-30, doi: 10.1016/S0012-365X(98)00089-2. |
[3] | T. Böhme, J. Harant and M. Tkáč, On certain Hamiltonian cycles in planar graphs, J. Graph Theory 32 (1999) 81-96, doi: 10.1002/(SICI)1097-0118(199909)32:1<81::AID-JGT8>3.0.CO;2-9. |
[4] | V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215-228, doi: 10.1016/0012-365X(73)90138-6. |
[5] | Z. Gao, 2-connected coverings of bounded degree in 3-connected graphs, J. Graph Theory 20 (1995) 327-338, doi: 10.1002/jgt.3190200309. |
[6] | D.P. Sanders and Y. Zhao, On 2-connected spanning subgraphs with low maximum degree, J. Combin. Theory (B) 74 (1998) 64-86, doi: 10.1006/jctb.1998.1836. |
[7] | C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169-176, doi: 10.1002/jgt.3190070205. |
[8] | W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99-116, doi: 10.1090/S0002-9947-1956-0081471-8. |
Received 24 July 2000
Revised 19 July 2001
Close