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.