Article ID Journal Published Year Pages File Type
8902822 Discrete Mathematics 2018 7 Pages PDF
Abstract
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. If every k-connected graph with no k-contractible edge has either H1 or H2 as a subgraph, then an unordered pair of graphs {H1,H2} is said to be a forbidden pair for k-contractible edges. We prove that {K1+3K2,K1+(P3∪K2)} is a forbidden pair for 6-contractible edges, which is an extension of a previous result due to Ando and Kawarabayashi.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,