RESEARCH ARTICLE

Orthogonal factorizations of digraphs

  • Guizhen LIU
Expand
  • School of Mathematics, Shandong University, Jinan 250100, China

Received date: 15 Aug 2008

Accepted date: 30 Oct 2008

Published date: 05 Jun 2009

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg

Abstract

Let G be a digraph with vertex set V (G) and arc set E(G) and let g = (g-, g+) and f = (f-, f+) be pairs of positive integer-valued functions defined on V (G) such that g-(x)≤f-(x) and g+(x)≤f+(x) for each xV (G). A (g, f)-factor of G is a spanning subdigraph H of G such that g-(x)≤idH(x)≤f-(x) and g+(x)≤odH(x)≤f+(x) for each xV (H); a (g, f)-factorization of G is a partition of E(G) into arc-disjoint (g, f)-factors. Let ={F1,F2,,Fm} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each Fi, 1≤im, has exactly k arcs in common with H. In this paper it is proved that every (mg+m-1,mf-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 xV (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 xV (G). The results in this paper are in some sense best possible.

Cite this article

Guizhen LIU . Orthogonal factorizations of digraphs[J]. Frontiers of Mathematics in China, 2009 , 4(2) : 311 -323 . DOI: 10.1007/s11464-009-0011-y

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

DOI

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

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

Options
Outlines

/