Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902822 | Discrete Mathematics | 2018 | 7 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kiyoshi Ando,