首页   按字顺浏览 期刊浏览 卷期浏览 Some properties of 2‐threshold graphs
Some properties of 2‐threshold graphs

 

作者: P. L. Hammer,   N. V. R. Mahadev,   U. N. Peled,  

 

期刊: Networks  (WILEY Available online 1989)
卷期: Volume 19, issue 1  

页码: 17-23

 

ISSN:0028-3045

 

年代: 1989

 

DOI:10.1002/net.3230190103

 

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

 

数据来源: WILEY

 

摘要:

AbstractA 2‐threshold graph is defined to be the edge‐union of two threshold graphs. We prove that all chordless cycles of size at least 5 and their complements are forbidden for 2‐threshold graphs. We also obtain a sufficient condition for a 2‐threshold graph to be a comparability graph. Finally, we show that 2‐threshold graphs can have at most three cutpoints and obtain efficient algorithms to recognize, decompose and obtain a maximum stable set of 2‐threshold graphs with exactly thre

 

点击下载:  PDF (330KB)



返 回