Contractible edges in minimally \(k\)-connected graphs. (English) Zbl 1130.05032
Summary: An edge of a \(k\)-connected graph is said to be \(k\)-contractible if the contraction of the edge results in a \(k\)-connected graph. In this paper, we prove that a \((K_{1}+C_{4})\)-free minimally \(k\)-connected graph has a \(k\)-contractible edge, if incident to each vertex of degree \(k\), there is an edge which is not contained in a triangle. This implies two previous results, one due to C. Thomassen [J. Graph Theory 5, 351–354 (1981; Zbl 0498.05044)] and the other due to K. Kawarabayashi [Australas. J. Comb. 24, 165–168 (2001; Zbl 0982.05061)].
MSC:
| 05C40 | Connectivity |
References:
| [1] | Egawa, Y.; Enomoto, H.; Saito, A., Contractible edges in triangle-free graphs, Combinatorica, 6, 269-274 (1986) · Zbl 0607.05046 |
| [2] | Fontet, M., Graphes 4-essential, C. R. Acad. Sci. Paris, 287, 289-290 (1978) · Zbl 0386.05039 |
| [3] | Halin, R., A theorem on \(n\)-connected graphs, J. Combin. Theory, 7, 150-154 (1969) · Zbl 0172.25803 |
| [4] | Kawarabayashi, K., Note on \(k\)-contractible edges in \(k\)-connected graphs, Australas. J. Combin., 24, 165-168 (2001) · Zbl 0982.05061 |
| [5] | Mader, W., Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen, Arch. Math., 23, 219-224 (1972) · Zbl 0212.29402 |
| [6] | Mader, W., Disjunkte Fragmente in kritisch \(n\)-fach zusammenhängende Graphen, European J. Combin., 6, 353-359 (1985) · Zbl 0591.05047 |
| [7] | Mader, W., Generalizations of critical connectivity of graphs, Discrete Math., 72, 267-283 (1988) · Zbl 0664.05028 |
| [8] | Martinov, N., Uncontractible 4-connected graphs, J. Graph Theory, 6, 343-344 (1982) · Zbl 0499.05041 |
| [9] | Thomassen, C., Non-separating cycles in \(k\)-connected graphs, J. Graph Theory, 5, 351-354 (1981) · Zbl 0498.05044 |
| [10] | Tutte, W. T., A theory of 3-connected graphs, Indag. Math., 23, 441-455 (1961) · Zbl 0101.40903 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
