✦ LIBER ✦

Orthogonal (g,f)-factorizations in graphs

✍ Scribed by Guizhen Liu

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 362 KB
Volume: 143
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00033-f

No coin nor oath required. For personal study only.

✦ Synopsis

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(G). In this paper it is proved that for any m-matching M of an (mg + m -l,mf-m + 1)-graph G, there exists a (g,f)-factorization of G orthogonal to M.

📜 SIMILAR VOLUMES

Orthogonal (g, f)-factorizations in netw

Orthogonal (g, f)-factorizations in networks

✍ Peter Che Bor Lam; Guizhen Liu; Guojun Li; Wai Chee Shiu 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB 👁 1 views

Let G G G = (V V V, E E E) be a graph and let g g g and f f f be two integervalued functions defined on V V V such that k k k ≤ ≤ ≤ g g g(x x x) ≤ ≤ ≤ f f f(x x x) for all x x x ∈ ∈ ∈ V

Orthogonal factorizations of graphs

✍ Haodi Feng; Guizhen Liu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

## Abstract Let __G__ be a graph with vertex set __V__(__G__) and edge set __E__(__G__). Let __k__~1~, __k__~2~,…,__k__~m~ be positive integers. It is proved in this study that every [0,__k__~1~+…+__k__~__m__~−__m__+1]‐graph __G__ has a [0, __k__~i~]~1~^__m__^‐factorization orthogonal to any given

Orthogonal one-factorization graphs

✍ Jeffrey H. Dinitz 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 516 KB

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

✍ William Y.C. Chen 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 472 KB

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 gr

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.