Isolated toughness and path-factor uniform graphs (II)

被引:0
作者
Sizhong Zhou
Zhiren Sun
Qiuxiang Bian
机构
[1] Jiangsu University of Science and Technology,School of Science
[2] Nanjing Normal University,School of Mathematical Sciences
来源
Indian Journal of Pure and Applied Mathematics | 2023年 / 54卷
关键词
Graph; Isolated toughness; Edge-connectivity; Path-factor; Path-factor uniform graph.; 05C70; 05C38;
D O I
暂无
中图分类号
学科分类号
摘要
A spanning subgraph F of G is called a path-factor if each component of F is a path. A P≥k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{\ge k}$$\end{document}-factor of G means a path-factor such that each component is a path with at least k vertices, where k≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 2$$\end{document} is an integer. A graph G is called a P≥k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{\ge k}$$\end{document}-factor covered graph if for each e∈E(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e\in E(G)$$\end{document}, G has a P≥k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{\ge k}$$\end{document}-factor covering e. A graph G is called a P≥k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{\ge k}$$\end{document}-factor uniform graph if for any two different edges e1,e2∈E(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e_1,e_2\in E(G)$$\end{document}, G has a P≥k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{\ge k}$$\end{document}-factor covering e1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e_1$$\end{document} and avoiding e2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e_2$$\end{document}. In other word, a graph G is called a P≥k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{\ge k}$$\end{document}-factor uniform graph if for any e∈E(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e\in E(G)$$\end{document}, the graph G-e\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G-e$$\end{document} is a P≥k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{\ge k}$$\end{document}-factor covered graph. In this article, we demonstrate that (i) an (r+3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(r+3)$$\end{document}-edge-connected graph G is a P≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{\ge 2}$$\end{document}-factor uniform graph if its isolated toughness I(G)>r+32r+3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I(G)>\frac{r+3}{2r+3}$$\end{document}, where r is a nonnegative integer; (ii) an (r+3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(r+3)$$\end{document}-edge-connected graph G is a P≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_{\ge 3}$$\end{document}-factor uniform graph if its isolated toughness I(G)>3r+62r+3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I(G)>\frac{3r+6}{2r+3}$$\end{document}, where r is a nonnegative integer. Furthermore, we claim that these conditions on isolated toughness and edge-connectivity in our main results are best possible in some sense.
引用
收藏
页码:689 / 696
页数:7
相关论文
共 35 条
[1]  
Ando K(2002)Path factors inclaw-free graphs Discrete Mathematics 243 195-200
[2]  
Egawa Y(2021)Tight binding number bound for Information Processing Letters 172 106162-1158
[3]  
Kaneko A(2021)-factor uniform graphs International Journal of Intelligent Systems 36 1133-42
[4]  
Kawarabayashi K(1998)Tight bounds for the existence of path factors in network vulnerability parameter settings Journal of Graph Theory 28 39-1423
[5]  
Matsudae H(2010)An El-Zahár type condition ensuring path-factors Discrete Mathematics 310 1413-218
[6]  
Gao W(2003)Path factors and parallel knock-out schemes of almost claw-free graphs Journal of Combinatorial Theory, Series B 88 195-135
[7]  
Wang W(2004)A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two Discrete Mathematics 283 129-556
[8]  
Gao W(2008)Packing paths of length at least two Discussiones Mathematicae Graph Theory 28 551-389
[9]  
Wang W(2010)Path and cycle factors of cubic bipartite graphs Applied Mathematics Letters 23 385-2076
[10]  
Chen Y(2009)Component factors with large components in graphs Discrete Mathematics 309 2067-1834