ON 2-CONNECTED SPANNING SUBGRAPHS WITH LOW MAXIMUM DEGREE

Authors
Citation
Dp. Sanders et Y. Zhao, ON 2-CONNECTED SPANNING SUBGRAPHS WITH LOW MAXIMUM DEGREE, J COMB TH B, 74(1), 1998, pp. 64-86
Citations number
17
Categorie Soggetti
Mathematics,Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956 → ACNP
Volume
74
Issue
1
Year of publication
1998
Pages
64 - 86
Database
ISI
SICI code
0095-8956(1998)74:1<64:O2SSWL>2.0.ZU;2-F
Abstract
Given a graph G, let a k-trestle of G be a 2-connected spanning subgra ph of G of maximum degree at most k. Also, let chi(G) be the Euler cha racteristic of G. This paper shows that every 3-connected graph G has a (10-2 chi(G))-trestle. If chi(G)less than or equal to -5, this is im proved to 8-2 chi(G), and for chi(G)less than or equal to -10, this is further improved to 6-2 chi(G). This result is shown to be best possi ble for almost all values of chi(G) by the demonstration of 3-connecte d graphs embedded on each surface of Euler characteristic chi less tha n or equal to 0 which have no (5-2 chi)-trestle. Also, it is shown tha t a 4-connected graph embeddable on a surface with non-negative Euler characteristic has a 3-trestle, approaching a conjecture of Nash-Willi ams. (C) 1998 Academic Press.