Abstract
An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k 2-3k or morek-contractible edges.
Similar content being viewed by others
References
K. Ando, H. Enomoto andA. Saito, Contractible edges in 3-connected graphs,submitted.
M. Behzad, G. Chartrand andL. Lesniak-Foster,Graphs and Digraphs, Prindle, Weber & Schmidt, Boston MA, 1979.
B. Bollobás,Graph Theory, Springer-Verlag, New York NY, 1979.
C. Thomassen, Planarity and Duality of finite and infinite graphs,J. Combinatorial Theory Ser. B 29 (1980), 244–271.
C. Thomassen, Nonseparating cycles ink-connected graphs,J. Graph Theory 5 (1981), 351–354.
C. Thomassen andB. Toft, Induced non-separating cycles in graphs.J. Combinatorial Theory Ser. B 31 (1981), 199–224.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Egawa, Y., Enomoto, H. & Saito, A. Contractible edges in triangle-free graphs. Combinatorica 6, 269–274 (1986). https://doi.org/10.1007/BF02579387
Issue Date:
DOI: https://doi.org/10.1007/BF02579387