On removable edges in 3-connected cubic graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2012

On removable edges in 3-connected cubic graphs

Résumé

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.
Fichier principal
Vignette du fichier
RemovableEdgesCubic.pdf (107.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00516060 , version 1 (08-09-2010)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More