Please wait a minute...
Frontiers of Mathematics in China

ISSN 1673-3452

ISSN 1673-3576(Online)

CN 11-5739/O1

Postal Subscription Code 80-964

2018 Impact Factor: 0.565

Front Math Chin    2009, Vol. 4 Issue (2) : 311-323    https://doi.org/10.1007/s11464-009-0011-y
RESEARCH ARTICLE
Orthogonal factorizations of digraphs
Guizhen LIU()
School of Mathematics, Shandong University, Jinan 250100, China
 Download: PDF(154 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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 de?ned 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.

Keywords Digraph      (g, f)-factor      orthogonal factorization     
Corresponding Author(s): LIU Guizhen,Email:gzliu@sdu.edu.cn   
Issue Date: 05 June 2009
 Cite this article:   
Guizhen LIU. Orthogonal factorizations of digraphs[J]. Front Math Chin, 2009, 4(2): 311-323.
 URL:  
https://academic.hep.com.cn/fmc/EN/10.1007/s11464-009-0011-y
https://academic.hep.com.cn/fmc/EN/Y2009/V4/I2/311
1 Akiyama J, Kano M. Factors and factorizations of graphs—a survey. J Graph Theory , 1985, 9: 1-42
doi: 10.1002/jgt.3190090103
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: 10.1016/S0012-365X(97)00025-3
4 Feng H, Liu G. Orthogonal factorizations of graphs. J Graph Theory , 2002, 40(4): 267-276
doi: 10.1002/jgt.10048
5 Gallai T. Maximum-minimum S?tze and verallgemeinerte Factoren von Graphen. Acta Math Acad Sci Hungar , 1961, 12: 131-173
doi: 10.1007/BF02066678
6 Kano M. [a, b]-factorization of a graph. J Graph Theory , 1985, 9: 297-307
doi: 10.1002/jgt.3190090111
7 Lam P, Liu G, Shui W. Orthogonal (g, f)-factorizations in networks. Networks , 2000, 35(4): 274-278
doi: 10.1002/1097-0037(200007)35:4<274::AID-NET6>3.0.CO;2-6
8 Liu G. Orthogonal (g, f)-factorizations in graphs. Discrete Math , 1995, 143: 153-158
doi: 10.1016/0012-365X(94)00033-F
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: 10.1016/S0166-218X(02)00503-6
11 Tutte W T. The 1-factors of oriented graphs. Proc Amer Math Soc , 1953, 4: 922-931
doi: 10.2307/2031831
[1] Hongmei YAO, Li MA, Chunmeng LIU, Changjiang BU. Brualdi-type inclusion sets of Z-eigenvalues and lk,s-singular values for tensors[J]. Front. Math. China, 2020, 15(3): 601-612.
[2] Yanxia DONG,Erfang SHAN,Xiao MIN. Distance domination of generalized de Bruijn and Kautz digraphs[J]. Front. Math. China, 2017, 12(2): 339-357.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed