On Specific Factors in Graphs
Csilla Bujtás, Stanislav Jendrol′, Źsolt Tuza
Abstract
Abstract It is well known that if $$G = (V, E)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is a connected multigraph and $$X\subset V$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>X</mml:mi> <mml:mo>⊂</mml:mo> <mml:mi>V</mml:mi> </mml:mrow> </mml:math> is a subset of even order, then G contains a spanning forest H such that each vertex from X has an odd degree in H and all the other vertices have an even degree in H . This spanning forest may have isolated vertices. If this is not allowed in H , then the situation is much more complicated. In this paper, we study this problem and generalize the concepts of even-factors and odd-factors in a unified form.