An Alternative Proof of the $H$-Factor Theorem

Details An Alternative Proof of the $H$-Factor Theorem An Alternative Proof of the $H$-Factor Theorem

2011-04-27

arxiv.org/abs/1104.5113v1

Mathematics

Combinatorics

Scientific paper

Let $H: V(G) \rightarrow 2^{\mathbb{N}}$ be a set mapping for a graph $G$. Given a spanning subgraph $F$ of $G$, $F$ is called a {\it general factor} or an $H$-{\it factor} of $G$ if $d_{F}(x)\in H(x)$ for every vertex $x\in V(G)$. $H$-factor problems are, in general, $NP$-complete problems and imply many well-known factor problems (e.g., perfect matchings, $f$-factor problems and $(g, f)$-factor problems) as special cases. Lov\'asz [The factorization of graphs (II), Acta Math. Hungar., 23 (1972), 223--246] gave a structure description and obtained a deficiency formula for $H$-optimal subgraphs. In this note, we use a generalized alternating path method to give a structural characterization and provide an alternative and shorter proof of Lov\'asz's deficiency formula.

Affiliated with

Also associated with

No associations

Rating

An Alternative Proof of the $H$-Factor Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Alternative Proof of the $H$-Factor Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Alternative Proof of the $H$-Factor Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-475454