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)
返 回