Orthogonal factorizations of digraphs

Abstract

Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g⁻, g⁺) and ƒ = (ƒ⁻, ƒ⁺) be pairs of positive integer-valued functions defined on V(G) such that g⁻(x) ⩽ ƒ⁻(x) and g⁺(x) ⩽ ƒ⁺(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g⁻(x) ⩽ id_H(x) ⩽ ƒ⁻(x) and g⁺(x) ⩽ od_H(x) ⩽ ƒ⁺(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let = {F₁, F₂,…, F_m} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each F_i, 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g⁻(x), g⁺(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.

Keywords

Digraph / (g, f)-factor / orthogonal factorization

References

[1] Akiyama J., Kano M. Factors and factorizations of graphs—a survey. J Graph Theory, 1985, 9: 1-42.

[2] Alspach B., Heinrich K., Liu G. Dinitz J. H., Stinson D. R. Orthogonal factorizations of graphs. Contemporary Design Theory: A Collection of Surveys, 1992, New York: Wiley & Sons, 13-37.

[3] Anstee R. P., Caccetta L. Orthogonal matchings. Discrete Math, 1998, 179: 37-47.

[4] Feng H., Liu G. Orthogonal factorizations of graphs. J Graph Theory, 2002, 40(4): 267-276.

[5] Gallai T. Maximum-minimum Sätze and verallgemeinerte Factoren von Graphen. Acta Math Acad Sci Hungar, 1961, 12: 131-173.

[6] Kano M. [a, b]-factorization of a graph. J Graph Theory, 1985, 9: 297-307.

[7] Lam P., Liu G., Shui W. Orthogonal (g, f)-factorizations in networks. Networks, 2000, 35(4): 274-278.

[8] Liu G. Orthogonal (g, f)-factorizations in graphs. Discrete Math, 1995, 143: 153-158.

[9] Liu G. (g, f)-factorizations of bipartite graphs. Acta Math Scientia, 2001, 21B(3): 316-322.

[10] Liu G., Zhu B. Some problems on factorizations with constrains in bipartite graphs. Discrete Math, 2003, 128: 421-434.

[11] Tutte W. T. The 1-factors of oriented graphs. Proc Amer Math Soc, 1953, 4: 922-931.