首页   按字顺浏览 期刊浏览 卷期浏览 On the toughness index of planar graphs
On the toughness index of planar graphs

 

作者: Michael B. Dillencourt,  

 

期刊: Journal of Graph Theory  (WILEY Available online 1994)
卷期: Volume 18, issue 1  

页码: 103-107

 

ISSN:0364-9024

 

年代: 1994

 

DOI:10.1002/jgt.3190180110

 

出版商: Wiley Subscription Services, Inc., A Wiley Company

 

数据来源: WILEY

 

摘要:

AbstractThetoughness indexτ(G) of a graphGis defined to be the largest integertsuch that for anyS⊆V(G) with |S|>t,c(G ‐ S)<|S| ‐t, wherec(G‐S) denotes the number of components ofG‐S. In particular, 1‐tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that ifGis a planar graph, then τ(G) ≥ 2 if and only ifGis 4‐connected. This result suggests that there may be a polynomial‐time algorithm for determining whether a planar graph is 1‐tough, even though the problem for general graphs is NP‐hard. The result can be restated as follows: a planar graph is 4‐connected if and only if it remains 1‐tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4‐connected planar

 

点击下载:  PDF (238KB)



返 回