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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2012, Article in press, pp.9. 〈10.1016/j.disc.2011.11.025〉
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00516060
Contributeur : Henri Thuillier <>
Soumis le : mercredi 8 septembre 2010 - 16:09:28
Dernière modification le : mercredi 29 novembre 2017 - 10:28:45
Document(s) archivé(s) le : jeudi 9 décembre 2010 - 02:48:14

Fichier

RemovableEdgesCubic.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

261

Téléchargements de fichiers

136