TY - JOUR

T1 - Even factor of a graph with a bounded number of components

AU - Niu, Zhaohong

AU - Xiong, Liming

PY - 2010/10

Y1 - 2010/10

N2 - Let G be a connected simple graph of order n, k a positive integer and n sufficiently large relative to k. An even factor of G 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.

AB - Let G be a connected simple graph of order n, k a positive integer and n sufficiently large relative to k. An even factor of G 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.

UR - http://www.scopus.com/inward/record.url?scp=78449301682&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:78449301682

SN - 1034-4942

VL - 48

SP - 269

EP - 279

JO - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

ER -