Skip to Main content Skip to Navigation
Journal articles

On removable edges in 3-connected cubic graphs

Abstract : A removable edge in a 3-connected cubic graph G is an edge e=uv such that the cubic graph obtained from G-{u,v} by adding an edge between the two neighbours of u distinct from v and an edge between the two neighbours of v disctinct from u is still 3-connected. Li and Wu [1] showed that a spanning tree in a 3-connected cubic graph avoids at least two removable edges, and Kang, Li and Wu [2] showed that a spanning tree contains at least two removable edges. We show here how to obtain these results easily from the structure of the sets of non removable edges and we give a characterization of the extremal graphs for these two results. [1] WU Jichang and LI Xueliang, Removable edges outside a spanning tree of a 3-connected 3-regular graph, Journal of Mathematical Study, 36(3), 2003, 223-229. [2] KANG Haiyan, WU Jichang and LI Guojun, Removable edges of a spanning tree in 3-connected 3-regular graphs, LNCS, 4613, 2007, 337-345.
Document type :
Journal articles
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/inria-00516060
Contributor : Henri Thuillier Connect in order to contact the contributor
Submitted on : Wednesday, September 8, 2010 - 4:09:28 PM
Last modification on : Saturday, June 25, 2022 - 10:11:24 AM
Long-term archiving on: : Thursday, December 9, 2010 - 2:48:14 AM

File

RemovableEdgesCubic.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Luc Fouquet, Henri Thuillier. On removable edges in 3-connected cubic graphs. Discrete Mathematics, Elsevier, 2012, Article in press, pp.9. ⟨10.1016/j.disc.2011.11.025⟩. ⟨inria-00516060⟩

Share

Metrics

Record views

140

Files downloads

193