Characterizing P⩾2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {P}}_{\geqslant 2}$$\end{document}-Factor Deleted Graphs with Respect to the Size or the Spectral Radius

被引:0
作者
Changlong Shen
机构
[1] Central China Normal University,Faculty of Mathematics and Statistics
关键词
-factor deleted; -factor deleted; Size; Spectral radius; 05C38; 05C50; 05C70;
D O I
10.1007/s40840-023-01619-7
中图分类号
学科分类号
摘要
A graph 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}$${\mathcal {P}}_{\geqslant k}$$\end{document}-factor if G has a spanning subgraph H such that every component of H is a path of order at least k. A graph G is P⩾k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {P}}_{\geqslant k}$$\end{document}-factor deleted if 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} 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}$${\mathcal {P}}_{\geqslant k}$$\end{document}-factor for each edge e of G. In this paper, we give two necessary and sufficient conditions defining 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}$${\mathcal {P}}_{\geqslant 2}$$\end{document}-factor deleted graph and 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}$${\mathcal {P}}_{\geqslant 3}$$\end{document}-factor deleted graph, respectively. Based on the result of P⩾2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {P}}_{\geqslant 2}$$\end{document}-factor deleted graphs, we establish respectively a lower bound on the size and a lower bound on the spectral radius to ensure whether or not a graph is P⩾2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {P}}_{\geqslant 2}$$\end{document}-factor deleted. Furthermore, by constructing extremal graphs, we show that all the above bounds are best possible.
引用
收藏
相关论文
共 42 条
  • [1] Akiyama J(1980)On a 1,2-factor of a graph TRU Math. 16 97-102
  • [2] Avis D(2016)Spectral condition for Hamiltonicity of a graph Linear Algebra Appl. 494 70-79
  • [3] Era H(2005)Eigenvalues and perfect matchings Linear Algebra Appl. 395 155-162
  • [4] Benediktovich VI(2009)Matchings in regular graphs from eigenvalue J. Combin. Theory, Ser. B 99 287-297
  • [5] Brouwer AE(2010)Spectral radius and Hamiltonicity of graphs Linear Algebra Appl. 432 2170-2173
  • [6] Haemers WH(2003)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 195-218
  • [7] Cioabǎ SM(2004)Packing paths of length at least two Discrete Math. 283 129-135
  • [8] Gregory DA(2021)Characterizing Discrete Math. 344 349-355
  • [9] Haemers WH(2012)-factor and J. Graph Theory 69 316-324
  • [10] Fiedler M(2020)-factor covered graphs with respect to the size or the spectral radius Linear Algebra Appl. 614 21-40