A Characterization of Graphs Having All (g, f)-Factors

✍ Scribed by Thomas Niessen

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 310 KB
• Volume: 72
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1997.1797

✦ Synopsis

Let G be a graph with vertex set V and let g, f : V Ä Z + . We say that G has all ( g, f )-factors if G has an h-factor for every h: V Ä Z + such that g(v) h(v) f (v) for every v # V and at least one such h exists. In this note, we derive from Tutte's f-factor theorem a similar characterization for the property of having all ( g, f )-factors. An analogous result for parity-factors is presented also.

1998 Academic Press

Let G be a finite graph with possible multiple edges and loops and let g, f :

. By e G (U, W) we denote the number of edges of G joining a vertex of U to a vertex of W.

Lova sz [6] gave a characterization of graphs having a ( g, f )-factor and thereby he generalized Tutte's f-factor theorem [8]. In [9] Tutte showed that the ( g, f )-factor theorem can be derived from the f-factor theorem. Given positive integers a and b, the f-factor theorem has been applied in [4] and [5] to obtain conditions implying the existence of h-factors for every h: V Ä [a, a+1, ..., b] with h(V )#0 (mod 2). More generally, one can ask for the existence of h-factors, where h: V Ä Z + is any function such that g(v) h(v) f (v) for every v # V and h(V )#0 (mod 2). The aim of this note is to present a characterization of graphs having these factors. The result will be proved using Tutte's theorem, and so the f-factor theorem is also self-refining in this direction.

In the following let g, f: V Ä Z + such that there exists a function h: V Ä Z + with g(v) h(v) f (v) for every vertex v # V and h(V)#0 (mod 2). We will say that G has all ( g, f )-factors if and only if G has an h-factor for every h described above.