Reduced graphs of diameter two
作者:
Hong‐Jian Lai,
期刊:
Journal of Graph Theory
(WILEY Available online 1990)
卷期:
Volume 14,
issue 1
页码: 77-87
ISSN:0364-9024
年代: 1990
DOI:10.1002/jgt.3190140109
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractA graphHiscollapsibleif for every subset X ⊆V(H), Hhas a spanning connected subgraph whose set of odd‐degree vertices is X. In any graphGthere is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction ofGis areducedgraph. Interest in reduced graphs arises from the fact [4] that a graphGhas a spanning closed trail if and only if its corresponding reduced graph has a spanning closed trail. The concept can also be applied to study hamiltonian line graphs [11] or double cycle covers [8]. In this article, we characterize the reduced graphs of diameter two. As applications, we obtain prior results in [12] and [14], and show that every 2‐edge‐connected graph with diameter at most two either admits a double cycle cover with three even subgraphs or is isomorphic to the Peterse
点击下载:
PDF
(444KB)
返 回