Sun toughness and path-factor uniform graphs

Liu, Hongxia

doi:10.1051/ro/2022201

Liu, Hongxia

RAIRO. Operations Research, Tome 56 (2022) no. 6, pp. 4057-4062

Résumé

A path-factor is a spanning subgraph F of G such that each component of F is a path of order at least two. Let k be an integer with k ≥ 2. A P$$-factor is a spanning subgraph of G whose components are paths of order at least k. A graph G is called a P$$-factor covered graph if for any edge e of G, G admits a P$$-factor covering e. A graph G is called a P$$-factor uniform graph if for any two distinct edges e₁ and e₂ of G, G has a P$$-factor covering e₁ and excluding e₂. In this article, we claim that (1) a 4-edge-connected graph G is a P_≥3-factor uniform graph if its sun toughness s(G) ≥ 1; (2) a 4-connected graph G is a P_≥3-factor uniform graph if its sun toughness $s (G) > \frac{4}{5}$ .

MR Zbl

DOI : 10.1051/ro/2022201

Classification : 05C70, 05C38
Keywords: Graph, edge-connectivity, connectivity, Sun toughness, $$_≥3-factor, $$_≥3-factor uniform graph

@article{RO_2022__56_6_4057_0,
     author = {Liu, Hongxia},
     title = {Sun toughness and path-factor uniform graphs},
     journal = {RAIRO. Operations Research},
     pages = {4057--4062},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {6},
     doi = {10.1051/ro/2022201},
     mrnumber = {4515155},
     zbl = {1531.05205},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022201/}
}

TY  - JOUR
AU  - Liu, Hongxia
TI  - Sun toughness and path-factor uniform graphs
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 4057
EP  - 4062
VL  - 56
IS  - 6
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022201/
DO  - 10.1051/ro/2022201
LA  - en
ID  - RO_2022__56_6_4057_0
ER  -

%0 Journal Article
%A Liu, Hongxia
%T Sun toughness and path-factor uniform graphs
%J RAIRO. Operations Research
%D 2022
%P 4057-4062
%V 56
%N 6
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022201/
%R 10.1051/ro/2022201
%G en
%F RO_2022__56_6_4057_0

Liu, Hongxia. Sun toughness and path-factor uniform graphs. RAIRO. Operations Research, Tome 56 (2022) no. 6, pp. 4057-4062. doi: 10.1051/ro/2022201

Bibliographie
Cité par

[1] W. Gao and W. Wang, Tight binding number bound for $P_{\geq 3}$ -factor uniform graphs. Inf. Process. Lett. 172 (2021) 106162. | MR | Zbl | DOI

[2] W. Gao, L. Liang and Y. Chen, An isolated toughness condition for graphs to be fractional $(k, m)$ -deleted graphs. Util. Math. 105 (2017) 303–316. | MR | Zbl

[3] A. Kaneko, A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two. J. Combin. Theory Ser. B 88 (2003) 195–218. | MR | Zbl | DOI

[4] M. Kano, G. Y. Katona and Z. Király, Packing paths of length at least two. Discrete Math. 283 (2004) 129–135. | MR | Zbl | DOI

[5] M. Kano, H. Lu and Q. Yu, Component factors with large components in graphs. Appl. Math. Lett. 23 (2010) 385–389. | MR | Zbl | DOI

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

[7] S. Wang and W. Zhang, On $k$ -orthogonal factorizations in networks. RAIRO-Oper. Res. 55 (2021) 969–977. | MR | Zbl | Numdam | DOI

[8] S. Wang and W. Zhang, Isolated toughness for path factors in networks. RAIRO-Oper. Res. 56 (2022) 2613–2619. | MR | Zbl | Numdam | DOI

[9] D. Woodall, The binding number of a graph and its Anderson number. J. Combin. Theory Ser. B 15 (1973) 225–255. | MR | Zbl | DOI

[10] J. Yang, Y. Ma and G. Liu, Fractional $(g, f)$ -factors in graphs. Appl. Math. A J. Chin. Univ. Ser. A 16 (2001) 385–390. | MR | Zbl

[11] Y. Yuan and R. Hao, Independence number, connectivity and all fractional $(a, b, k)$ -critical graphs. Discuss. Math. Graph Theory 39 (2019) 183–190. | MR | Zbl | DOI

[12] H. Zhang and S. Zhou, Characterizations for $P_{\geq 2}$ -factor and $P_{\geq 3}$ -factor covered graphs. Discrete Math. 309 (2009) 2067–2076. | MR | Zbl | DOI

[13] S. Zhou, Path factors and neighborhoods of independent sets in graphs. Acta Math. Appl. Sin. Engl. Ser. (2022) DOI: . | DOI | MR | Zbl

[14] S. Zhou, A result on fractional $(a, b, k)$ -critical covered graphs. Acta Math. Appl. Sin. Engl. Ser. 37 (2021) 657–664. | MR | Zbl | DOI

[15] S. Zhou, Remarks on restricted fractional $(g, f)$ -factors in graphs. Discrete Appl. Math. (2022) DOI: . | DOI | MR | Zbl

[16] S. Zhou, A neighborhood union condition for fractional $(a, b, k)$ -critical covered graphs. Discrete Appl. Math. 323 (2022) 343–348. | MR | Zbl | DOI

[17] S. Zhou, A note of generalization of fractional ID-factor-critical graphs. Fundam. Inform. 187 (2022) 61–69. | MR | Zbl | DOI

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

[19] S. Zhou and Q. Bian, The existence of path-factor uniform graphs with large connectivity. RAIRO-Oper. Res. 56 (2022) 2919–2927. | MR | Zbl | Numdam | DOI

[20] S. Zhou, Q. Bian and Q. Pan, Path factors in subgraphs. Discrete Appl. Math. 319 (2022) 183–191. | MR | Zbl | DOI

[21] S. Zhou, H. Liu and Y. Xu, A note on fractional ID- $[a, b]$ -factor-critical covered graphs. Discrete Appl. Math. 319 (2022) 511–516. | MR | Zbl | DOI

[22] S. Zhou, Z. Sun and Q. Bian, Isolated toughness and path-factor uniform graphs (II). Indian J. Pure Appl. Math. (2022) DOI: . | DOI | MR | Zbl

[23] S. Zhou, Z. Sun and F. Yang, A result on $P_{\geq 3}$ -factor uniform graphs. Proc. Rom. Acad. Ser. A: Math. Phys. Tech. Sci. Inf. Sci. 23 (2022) 3–8. | MR | Zbl

[24] S. Zhou, J. Wu and Q. Bian, On path-factor critical deleted (or covered) graphs. Aequationes Math. 96 (2022) 795–802. | MR | Zbl | DOI

[25] S. Zhou, J. Wu and Y. Xu, Toughness, isolated toughness and path factors in graphs. Bull. Aust. Math. Soc. 106 (2022) 195–202. | MR | Zbl | DOI

Cité par Sources :