Article
Supereulerian graphs, independent sets, and degree-sum conditions
Discrete Mathematics
(1998)
Abstract
A graph is supereulerian if it contains a spanning closed trail. A graph G is collapsible if for every even subset R ⊆ V(G), there is a spanning connected subgraph of G whose set of odd degree vertices is R. The graph K1 is regarded as a trivial collapsible graph. A graph is reduced if it contains no nontrivial collapsible subgraphs. In this paper, we study the independence numbers of reduced graphs. As an application, we also obtain new degree-sum conditions for supereulerian graphs and collapsible graphs.
Disciplines
Publication Date
January, 1998
DOI
https://doi.org/10.1016/S0012-365X(97)00028-9
Publisher Statement
Note: full-text not available due to publisher restrictions. Link takes you to an external site where you can purchase the article or borrow it from a local library.
Citation Information
Zhi-Hong Chen. "Supereulerian graphs, independent sets, and degree-sum conditions" Discrete Mathematics Vol. 179 Iss. 1-3 (1998) p. 73 - 87 ISSN: 0012-365X Available at: http://works.bepress.com/zhi_hong_chen/36/