The existence of subdigraphs with orthogonal factorizations in digraphs

Sizhong Zhou; Quanru Pan; Sizhong Zhou; Quanru Pan

doi:10.3934/math.2021075

AIMS Mathematics

2021, Volume 6, Issue 2: 1223-1233. doi: 10.3934/math.2021075

Previous Article Next Article

Research article

The existence of subdigraphs with orthogonal factorizations in digraphs

Sizhong Zhou ,
Quanru Pan ^,

School of Science, Jiangsu University of Science and Technology, Zhenjiang, Jiangsu 212100, China

Received: 17 September 2020 Accepted: 01 November 2020 Published: 12 November 2020
MSC : 05C70, 05C20, 68M10

Let $G$ be a $[0, k_1+k_2+\cdots+k_m-n+1]$-digraph and $H_1, H_2, \cdots, H_r$ be $r$ vertex-disjoint $n$-subdigraphs of $G$, where $m, n, r$ and $k_i$ ($1\leq i\leq m$) are positive integers satisfying $1\leq n\leq m$ and $k_1\geq k_2\geq\cdots\geq k_m\geq r+1$. In this article, we verify that there exists a subdigraph $R$ of $G$ such that $R$ possesses a $[0, k_i]_1^{n}$-factorization orthogonal to every $H_i$ for $1\leq i\leq r$.
- network,
- digraph,
- subdigraph,
- factor,
- orthogonal factorization
Citation: Sizhong Zhou, Quanru Pan. The existence of subdigraphs with orthogonal factorizations in digraphs[J]. AIMS Mathematics, 2021, 6(2): 1223-1233. doi: 10.3934/math.2021075

Related Papers:

Abstract

Let $G$ be a $[0, k_1+k_2+\cdots+k_m-n+1]$-digraph and $H_1, H_2, \cdots, H_r$ be $r$ vertex-disjoint $n$-subdigraphs of $G$, where $m, n, r$ and $k_i$ ($1\leq i\leq m$) are positive integers satisfying $1\leq n\leq m$ and $k_1\geq k_2\geq\cdots\geq k_m\geq r+1$. In this article, we verify that there exists a subdigraph $R$ of $G$ such that $R$ possesses a $[0, k_i]_1^{n}$-factorization orthogonal to every $H_i$ for $1\leq i\leq r$.

References

[1]	Y. Egawa, M. Kano, Sufficient conditions for graphs to have (g, f)-factors, Discrete Math., 151 (1996), 87-90. doi: 10.1016/0012-365X(94)00085-W
[2]	W. Gao, J. Guirao, Y. Chen, A toughness condition for fractional (k, m)-deleted graphs revisited, Acta Mathematica Sinica, English Series, 35 (2019), 1227-1237. doi: 10.1007/s10114-019-8169-z
[3]	W. Gao, W. Wang, D. Dimitrov, Toughness condition for a graph to be all fractional (g, f, n)-critical deleted, Filomat, 33 (2019), 2735-2746. doi: 10.2298/FIL1909735G
[4]	X. Lv, A degree condition for fractional (g, f, n)-critical covered graphs, AIMS Mathematics, 5 (2020), 872-878. doi: 10.3934/math.2020059
[5]	S. Zhou, Z. Sun, H. Ye, A toughness condition for fractional (k, m)-deleted graphs, Inform. Process. Lett., 113 (2013), 255-259. doi: 10.1016/j.ipl.2013.01.021
[6]	S. Zhou, Z. Sun, Q. Pan, A sufficient condition for the existence of restricted fractional (g, f)-factors in graphs, Problems of Information Transmission, 56 (2020), in press.
[7]	S. Zhou, Remarks on path factors in graphs, RAIRO-Operations Research, 54 (2020), 1827-1834. doi: 10.1051/ro/2019111
[8]	S. Zhou, Binding numbers and restricted fractional (g, f)-factors in graphs, Discrete Applied Mathematics, 2020.
[9]	S. Zhou, F. Yang, L. Xu, Two sufficient conditions for the existence of path factors in graphs, Sci. Iran., 26 (2019), 3510-3514.
[10]	R. Ma, H. Gao, On (g, f)-factorizations of graphs, Applied Mathematics and Mechanics, English Edition, 18 (1997), 407-410.
[11]	G. Liu, H. Long, Randomly orthogonal (g, f)-factorizations in graphs, Acta Mathematicae Applicatae Sinica, English Series, 18 (2002), 489-494.
[12]	G. Liu, B. Zhu, Some problems on factorizations with constraints in bipartite graphs, Discrete Applied Mathematics, 128 (2003), 421-434. doi: 10.1016/S0166-218X(02)00503-6
[13]	S. Zhou, Remarks on orthogonal factorizations of digraphs, International Journal of Computer Mathematics, 91 (2014), 2109-2117. doi: 10.1080/00207160.2014.881993
[14]	B. Alspach, K. Heinrich, G. Liu, Contemporary Design Theory-A Collection of Surveys, John Wiley and Sons, New York, 1992, 13-37.
[15]	S. Wang, W. Zhang, Research on fractional critical covered graphs, Problems of Information Transmission, 56 (2020), 270-277. doi: 10.1134/S0032946020030047
[16]	S. Zhou, T. Zhang, Z. Xu, Subgraphs with orthogonal factorizations in graphs, Discrete Applied Mathematics, 286 (2020), 29-34. doi: 10.1016/j.dam.2019.12.011
[17]	S. Zhou, Y. Xu, Z. Sun, Degree conditions for fractional (a, b, k)-critical covered graphs, Inform. Process. Lett., 152 (2019), 105838. doi: 10.1016/j.ipl.2019.105838
[18]	X. Zhou, T. Nishizeki, Edge-coloring and f-coloring for Vatious Classes of Graphs, Lecture Notes in Computer Science, 834 (1994), 199-207. doi: 10.1007/3-540-58325-4_182
[19]	J. Horton, Room designs and one-factorizations, Aequationes Math., 22 (1981), 56-63. doi: 10.1007/BF02190160
[20]	L. Euler, Recherches sur une nouveau espece de quarres magiques, in Leonhardi Euleri Opera Omnia. Ser. Prima., 7 (1923), 291-392.
[21]	S. Zhou, Z. Sun, Binding number conditions for P_≥2-factor and P_≥3-factor uniform graphs, Discrete Mathematics, 343 (2020), 111715. doi: 10.1016/j.disc.2019.111715
[22]	S. Zhou, Z. Sun, Some existence theorems on path factors with given properties in graphs, Acta Mathematica Sinica, English Series, 36 (2020), 917-928. doi: 10.1007/s10114-020-9224-5
[23]	S. Zhou, Some results on path-factor critical avoidable graphs, Discussiones Mathematicae Graph Theory, 2020.
[24]	M. Kouider, Z. Lonc, Stability number and [a, b]-factors in graphs, J. Graph Theor., 46 (2004), 254-264. doi: 10.1002/jgt.20008
[25]	G. Yan, J. Pan, C. Wong, T. Tokuda, Decomposition of graphs into (g, f)-factors, Graph. Combinator., 16 (2000), 117-126. doi: 10.1007/s003730050009
[26]	G. Liu, Orthogonal (g, f)-factorizations in graphs, Discrete Mathematics, 143 (1995), 153-158.
[27]	P. C. B. Lam, G. Liu, G. Li, W. Shiu, Orthogonal (g, f)-factorizations in networks, Networks, 35 (2000), 274-278.
[28]	H. Feng, G. Liu, Orthogonal factorizations of graphs, J. Graph Theor., 40 (2002), 267-276. doi: 10.1002/jgt.10048
[29]	C. Wang, Orthogonal factorizations in networks, Int. J. Comput. Math., 88 (2011), 476-483. doi: 10.1080/00207161003678498
[30]	G. Liu, Orthogonal factorizations of digraphs, Front. Math. China, 4 (2009), 311-323. doi: 10.1007/s11464-009-0011-y
[31]	C. Wang, Subdigraphs with orthogonal factorizations of digraphs, Eur. J. Combin., 33 (2012), 1015-1021. doi: 10.1016/j.ejc.2012.01.010
[32]	S. Zhou, Q. Bian, Subdigraphs with orthogonal factorizations of digraphs (II), Eur. J. Combin., 36 (2014), 198-205. doi: 10.1016/j.ejc.2013.06.042
[33]	S. Zhou, Z. Sun, Z. Xu, A result on r-orthogonal factorizations in digraphs, Eur. J. Combin., 65 (2017), 15-23. doi: 10.1016/j.ejc.2017.05.001

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)