๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Maximum (g,f)-factors of a general graph

โœ Scribed by William Y.C. Chen

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
472 KB
Volume
91
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Chen, W. Y. C., Maximum (g, f)-factors of a general graph, Discrete Mathematics 91 (1991) l-7. This paper presents a characterization of maximum (g, f)-factors of a general graph in which multiple edges and loops are allowed. An analogous characterization of the minimum (g,f)-factors of a general graph is also presented. In addition, we obtain a transformation theorem for any two general graphs on the same vertex set. As special cases, we have the transformation theorems for both maximum (g, f)-factors and minimum (g, f)-factors. Our results generalize some of C. Berge's results on maximum matchings and maximum c-matchings of a multiple graph.

๐Ÿ“œ SIMILAR VOLUMES

On f-factors of a graph
On f-factors of a graph
โœ Jialong Lan; Wai-Kai Chen ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 404 KB

## This paper probes the relations between f-factors and subgraphs and their degree sequences in a graph when the graph has the odd-cycle property and contains no self-loop. Useful results are derived which greatly simplify tests of the existence of f-factors. z. zntrodactic?n

Orthogonal (g,f)-factorizations in graph
Orthogonal (g,f)-factorizations in graphs
โœ Guizhen Liu ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 362 KB

LetGbeagraphandletF={F,,F,,..., F,,,} and H be a factorization and a subgraph of G, respectively. If H has exactly one edge in common with Fi for all i, 1 < i < m, then we say that F is orthogonal to H. Let g andf be two integer-valued functions defined on V(G) such that g(x) < f(x) for every x E V(

A Characterization of Graphs Having All
A Characterization of Graphs Having All (g, f)-Factors
โœ Thomas Niessen ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 310 KB

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

Sufficient conditions for graphs to have
Sufficient conditions for graphs to have (g, f)-factors
โœ Yoshimi Egawa; Mikio Kano ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 170 KB

We give sufficient conditions for a graph to have a (g,f)-factor. For example, we prove that a graph G has a (g,f)-factor if g(v) < f(v) for all vertices v of G and g(x)/deg~(x) <~ f(y)/deg~(y) for all adjacent vertices x and y of G.

Algorithms for a maximum clique and a ma
Algorithms for a maximum clique and a maximum independent set of a circle graph
โœ F. Gavril ๐Ÿ“‚ Article ๐Ÿ“… 1973 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 523 KB

## Abstract Consider a family of chords in a circle. A circle graph is obtained by representing each chord by a vertex, two vertices being connected by an edge when the corresponding chords intersect. In this paper, we describe efficient algorithms for finding a maximum clique and a maximum indepen