Distribution of contractible edges in k-connected graphs
type: Item
instance of: scholarly article
title: Distribution of contractible edges in k-connected graphs
zbMATH Open document ID: 0687.05028
DOI: 10.1016/0095-8956(90)90126-K
author: Nathaniel Dean
published in: Journal of Combinatorial Theory. Series B
publication date: 1990-01-01T00:00:00Z
review text: Let G be a k-connected graph and let \(e=xy\) be an edge in g. The edge e is said to be k-contractible if identifying the vertices x and y results in a k-connected graph. The paper investigates the distribution of k- contractible edges in a graph G. It shows that, if G is a k-connected graph which is triangle-free or has minimum degree at least \(\lfloor 3k/2\rfloor\) then the subgraph of G induced by its k-contractible edges is a 2-connected spanning subgraph of G. Furthermore, if \(k\geq 3\), then G contains an induced cycle C such that all edges in C are k-contractible and V(C) is not a cutset for G.
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 4125431
zbMATH Keywords: k-contractible
zbMATH Keywords: k-connected graph
reviewed by: R. E. L. Aldred
MaRDI profile type: Publication
cites work: Contractible edges in 3-connected graphs
cites work: Q3097395
cites work: Contractible edges in triangle-free graphs
cites work: Generalizaions of critical connectivity of graphs
cites work: Nonseparating cycles inK-Connected graphs
cites work: Non-separating induced cycles in graphs
description: scientific article; zbMATH DE number 4125431