On $k$-orthogonal factorizations in networks

Wang, Sufang; Zhang, Wei

doi:10.1051/ro/2021037

On

k

-orthogonal factorizations in networks

Wang, Sufang ; Zhang, Wei

RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 969-977

Résumé

Let m, n, k, r and k$$ (1 ≤i ≤ m) are positive integers such that 1 ≤n ≤ m and k₁ ≥ k₂ ≥⋯≥k_m ≥ (r + 1)k. Let G be a graph with vertex set V(G) and edge set E(G), and H₁, H₂,⋯,H$$ be r vertex-disjoint $n k$ -subgraphs of G. In this article, we demonstrate that a graph G with maximum degree at most $\sum_{i = 1}^{m} k_{i} - (n - 1) k$ has a set $ℱ = {F_{1}, \dots, F_{n}}$ of n pairwise edge-disjoint factors of G such that F$$ has maximum degree at most k$$ for 1 ≤ i ≤ n and $ℱ$ is k-orthogonal to every H$$ for 1 ≤ j ≤ r.

MR Zbl

DOI : 10.1051/ro/2021037

Classification : 05C70, 68M10, 68R10
Keywords: Graph, network, factor, orthogonal factorization

@article{RO_2021__55_2_969_0,
     author = {Wang, Sufang and Zhang, Wei},
     title = {On $k$-orthogonal factorizations in networks},
     journal = {RAIRO. Operations Research},
     pages = {969--977},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {2},
     doi = {10.1051/ro/2021037},
     mrnumber = {4253784},
     zbl = {1468.05240},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021037/}
}

TY  - JOUR
AU  - Wang, Sufang
AU  - Zhang, Wei
TI  - On $k$-orthogonal factorizations in networks
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 969
EP  - 977
VL  - 55
IS  - 2
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021037/
DO  - 10.1051/ro/2021037
LA  - en
ID  - RO_2021__55_2_969_0
ER  -

%0 Journal Article
%A Wang, Sufang
%A Zhang, Wei
%T On $k$-orthogonal factorizations in networks
%J RAIRO. Operations Research
%D 2021
%P 969-977
%V 55
%N 2
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021037/
%R 10.1051/ro/2021037
%G en
%F RO_2021__55_2_969_0

Wang, Sufang; Zhang, Wei. On $k$-orthogonal factorizations in networks. RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 969-977. doi: 10.1051/ro/2021037

Bibliographie
Cité par

[1] B. Alspach, K. Heinrich and G. Liu, Contemporary Design Theory – A Collection of Surveys. John Wiley and Sons, New York (1992) 13–37.

[2] H. Feng, On orthogonal $(0, f)$ -factorizations. Acta Math. Sci. Eng. Ser. 19 (1999) 332–336. | MR | Zbl | DOI

[3] H. Feng and G. Liu, Orthogonal factorizations of graphs. J. Graph Theory 40 (2002) 267–276. | MR | Zbl | DOI

[4] W. Gao, J. Guirao and Y. Chen, A toughness condition for fractional $(k, m)$ -deleted graphs revisited. Acta Math. Sinica Eng. Ser. 35 (2019) 1227–1237. | MR | Zbl | DOI

[5] W. Gao, W. Wang and D. Dimitrov, Toughness condition for a graph to be all fractional $(g, f, n)$ -critical deleted. Filomat 33 (2019) 2735–2746. | MR | Zbl | DOI

[6] M. Kano, [ $a, b$ ]-factorizations of a graph. J. Graph Theory 9 (1985) 129–146. | MR | Zbl | DOI

[7] P. C. B. Lam, G. Liu, G. Li and W. Shiu, Orthogonal $(g, f)$ -factorizations in networks. Networks 35 (2000) 274–278. | MR | Zbl | DOI

[8] G. Li and G. Liu, A generalization of orthogonal factorizations in graphs. Acta Math. Sinica Eng. Ser. 17 (2001) 669–678. | MR | Zbl | DOI

[9] G. Li and G. Liu, $(g, f)$ -factorizations orthogonal to a subgraph in graphs. Sci. Chin. Ser. A 41 (1998) 267–272. | MR | Zbl | DOI

[10] G. Li, C. Chen and G. Yu, Orthogonal factorizations of graphs. Discrete Math. 245 (2002) 173–194. | MR | Zbl | DOI

[11] G. Liu, Orthogonal $(g, f)$ -factorizations in graphs. Discrete Math. 143 (1995) 153–158. | MR | Zbl | DOI

[12] G. Liu and H. Long, Randomly orthogonal $(g, f)$ -factorizations in graphs. 18 (2002) 489–494. | MR | Zbl | DOI

[13] G. Liu and B. Zhu, Some problems on factorizations with constraints in bipartite graphs. Discrete Appl. Math. 128 (2003) 421–434. | MR | Zbl | DOI

[14] X. Lv, A degree condition for fractional $(g, f, n)$ -critical covered graphs. AIMS Math. 5 (2020) 872–878. | MR | Zbl | DOI

[15] R. Matsubara, H. Matsuda, N. Matsuo, K. Noguchi and K. Ozeki, [ $a, b$ ]-factors of graphs on surfaces. Discrete Math. 342 (2019) 1979–1988. | MR | Zbl | DOI

[16] M. Plummer and A. Saito, Toughness, binding number and restricted matching extension in a graph. Discrete Math. 340 (2017) 2665–2672. | MR | Zbl | DOI

[17] Z. Sun and S. Zhou, A generalization of orthogonal factorizations in digraphs. Inf. Process. Lett. 132 (2018) 49–54. | MR | Zbl | DOI

[18] C. Wang, Orthogonal factorizations in networks. Int. J. Comput. Math. 88 (2011) 476–483. | MR | Zbl | DOI

[19] C. Wang, Subgraphs with orthogonal factorizations and algorithms. Eur. J. Comb. 31 (2010) 1706–1713. | MR | Zbl | DOI

[20] S. Wang and W. Zhang, Research on fractional critical covered graphs. Prob. Inf. Transm. 56 (2020) 270–277. | Zbl | DOI

[21] G. Yan, J. Pan, C. Wong and T. Tokuda, Decomposition of graphs into $(g, f)$ -factors. Graphs Comb. 16 (2000) 117–126. | MR | Zbl | DOI

[22] Y. Yuan and R. Hao, Toughness condition for the existence of all fractional $(a, b, k)$ -critical graphs. Discrete Math. 342 (2019) 2308–2314. | MR | Zbl | DOI

[23] S. Zhou, Remarks on orthogonal factorizations of digraphs. Int. J. Comput. Math. 91 (2014) 2109–2117. | MR | Zbl | DOI

[24] S. Zhou, Some results about component factors in graphs. RAIRO:OR 53 (2019) 723–730. | MR | Zbl | Numdam | DOI

[25] S. Zhou, Binding numbers and restricted fractional $(g, f)$ -factors in graphs. Discrete Appl. Math. DOI: (2020). | DOI | MR | Zbl

[26] S. Zhou, Remarks on path factors in graphs. RAIRO:OR 54 (2020) 1827–1834. | MR | Zbl | Numdam | DOI

[27] S. Zhou, Some results on path-factor critical avoidable graphs. Discussiones Mathematicae Graph Theory. DOI: (2020). | DOI | MR | Zbl

[28] S. Zhou, Q. Bian and Z. Sun, Two sufficient conditions for component factors in graphs. Discuss. Math. Graph Theory. DOI: (2021). | DOI | MR

[29] S. Zhou, H. Liu and Y. Xu, A note on fractional ID-[ $a, b$ ]-factor-critical covered graphs. Discrete Appl. Math. DOI: (2021). | DOI | MR | Zbl

[30] S. Zhou, H. Liu and T. Zhang, Randomly orthogonal factorizations with constraints in bipartite networks. Chaos Solitons Fractals 112 (2018) 31–35. | MR | Zbl | DOI

[31] S. Zhou and Z. Sun, Binding number conditions for $P_{\leq 2}$ -factor and $P_{\geq 3}$ -factor uniform graphs. Discrete Math. 343 (2020) 111715. | MR | Zbl | DOI

[32] S. Zhou and Z. Sun, Some existence theorems on path factors with given properties in graphs. Acta Math. Sinica Eng. Ser. 36 (2020) 917–928. | MR | Zbl | DOI

[33] S. Zhou, Y. Xu and Z. Sun, Degree conditions for fractional $(a, b, k)$ -critical covered graphs. Inf. Process. Lett. 152 (2019) 105838. | MR | Zbl | DOI

[34] S. Zhou, Z. Sun and Q. Pan, A sufficient condition for the existence of restricted fractional $(g, f)$ -factors in graphs. Prob. Inf. Transm. 56 (2020) 332–344. | MR | Zbl | DOI

[35] S. Zhou, T. Zhang and Z. Xu, Subgraphs with orthogonal factorizations in graphs. Discrete Appl. Math. 286 (2020) 29–34. | MR | Zbl | DOI

Cité par Sources :