Even factor of a graph with a bounded number of components
Zhaohong Niu, Liming Xiong · 2010
Let G be a connected simple graph of order n, k a positive integer and n sufficiently large relative to k. AnevenfactorofG is a spanning subgraph of G in which every vertex has even positive degree. In this paper, we prove that if δ(G) ≥⌊n/k⌋−1, then the (collapsible) reduction G ′ of G satisfies |V (G ′)|≤k, and the preimage of each vertex of G ′ is nontrivial. We use this result to prove that if δ(G) ≥⌊n/k⌋−1, then G has an even factor with at most k components. Moreover, if G is 2-edge-connected and k ∈{1, 2, 3} such that δ(G) ≥⌊n/(3k +1)⌋−1, then G has an even factor with at most k components, which extends a theorem of Catlin [J. Graph Theory 12 (1988), 29–44]. Finally, we show that every 2-edgeconnected reduced graph of order n ≤ 3k +1 ≤ 10 has a spanning even subgraph with at most k components. All results are best possible. 1