کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648136 | 1342394 | 2012 | 8 صفحه PDF | دانلود رایگان |
A removable edge in a 3-connected cubic graph GG is an edge e=uve=uv such that the cubic graph obtained from G∖{u,v}G∖{u,v} by adding an edge between the two neighbours of uu distinct from vv and an edge between the two neighbours of vv distinct from uu is still 3-connected. Li and Wu (2003) [5] showed that a spanning tree in a 3-connected cubic graph avoids at least two removable edges, and Kang et al. (2007) [3] 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. We investigate a neighbouring problem by considering perfect matchings in place of spanning trees.
Journal: Discrete Mathematics - Volume 312, Issue 17, 6 September 2012, Pages 2652–2659