id: 05901731
dt: j
an: 05901731
au: Niu, Zhaohong; Xiong, Liming
ti: Even factor of a graph with a bounded number of components.
so: Australas. J. Comb. 48, 269-279 (2010).
py: 2010
pu: Published for the Combinatorial Mathematics Society of Australasia by the
    Centre for Discrete Mathematics and Computing, the University of
    Queensland, Brisbane, QLD
la: EN
cc: 
ut: even factor; spanning subgraph; reduced graph; spanning even subgraph
ci: Zbl 0659.05073
li: 
ab: Summary: 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)\ge\lfloor
    n/k\rfloor- 1$, then the (collapsible) reduction $G’$ of $G$
    satisfies $|V(G’)|\le k$, and the preimage of each vertex of $G’$
    is nontrivial. We use this result to prove that if $δ(G)\ge\lfloor
    n/k\rfloor- 1$, then $G$ has an even factor with at most $k$
    components. Moreover, if $G$ is 2-edge-connected and $k\in\{1,2,3\}$
    such that $δ(G)\lfloor n/(3k+ 1)\rfloor-1$, then $G$ has an even
    factor with at most $k$ components, which extends a theorem of {\it P.
    A. Catlin} [J. Graph Theory 12, No. 1, 29‒44 (1988; Zbl 0659.05073)].
    Finally, we show that every 2-edge-connected reduced graph of order
    $n\le 3k+ 1\le 10$ has a spanning even subgraph with at most $k$
    components. All results are best possible.
rv: