Contractible Edges in 3-Connected Cubic Graphs
Abstract
An edge in a 3-connected graph is contractible if the contraction is still -connected. Let be the set of contractible edges of , be the set of vertices adjacent to three vertices of a triangle △. It has been proved that in a 3-connected graph of order at least 5. In this note is a 3-connected cubic graph containing triangles, at least vertices and with every an independent set. Then . This is a bound better than under some conditions.
Communicated by Eddie Cheng
References
- 1. , Graph Theory with Application (Macmillan, 1976). Crossref, Google Scholar
- 2. , A theory of 3-connected graphs, Nederl. Akad. Wetensch. Proc. Ser. A 64 (1961) 441–455. Crossref, Google Scholar
- 3. , Zur Theoric der n-fach zusammenhangenden graphen, Abh. Marh. Sem. Univ. Hamburg 33 (1969) 133–164. Crossref, Google Scholar
- 4. , Contractible edges in triangle-free graphs, Combinatorica 3 (1986) 269–274. Crossref, Google Scholar
- 5. , Contractible edges in 3-connected graphs, J. Combin. Theory Ser. B 42 (1987) 87–93. Crossref, ISI, Google Scholar
- 6. , Contractible edges and removable edges in 3-connected graphs, Graphs and Combinatorics 35 (2019) 1375–1385. Crossref, ISI, Google Scholar


