Sufficient conditions for component factors in a graph

被引:3
作者
Chen, Hongzhang [1 ]
Lv, Xiaoyun [1 ]
Li, Jianxi [2 ]
机构
[1] Lanzhou Univ, Gansu Ctr Appl Math, Sch Math & Stat, Lanzhou, Gansu, Peoples R China
[2] Minnan Normal Univ, Sch Math & Stat, Zhangzhou, Fujian, Peoples R China
基金
中国国家自然科学基金;
关键词
Component factor; (Signless Laplacian) Spectral radius; Laplacian eigenvalue; Toughness; Perfect k-matching; EXISTENCE;
D O I
10.1007/s13226-024-00575-7
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a graph and H\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {H}$$\end{document} be a set of connected graphs. A spanning subgraph H of G is called an H\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {H}$$\end{document}-factor if each component of H is isomorphic to a member of H\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {H}$$\end{document}. In this paper, we first present a lower bound on the size (resp. the spectral radius) of G to guarantee that G has a {P2,Cn:n >= 3}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{P_2,\, C_n: n\ge 3\}$$\end{document}-factor (or a perfect k-matching for even k) and construct extremal graphs to show all this bounds are best possible. We then provide a lower bound on the signless laplacian spectral radius of G to ensure that G has a {K1,j:1 <= j <= k}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{K_{1,j}:1\le j\le k\}$$\end{document}-factor, 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. Moreover, we also provide some Laplacian eigenvalue (resp. toughness) conditions for the existence of {P2,Cn:n >= 3}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{P_2,\, C_{n}:n\ge 3\}$$\end{document}-factor, 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 and {K1,j:1 <= j <= k}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{K_{1,j}: 1\le j\le k\}$$\end{document}-factor in G, respectively. Some of our results extend or improve the related existing results.
引用
收藏
页数:12
相关论文
共 21 条
[1]   ON FACTORS WITH GIVEN COMPONENTS [J].
AMAHASHI, A ;
KANO, M .
DISCRETE MATHEMATICS, 1982, 42 (01) :1-6
[2]  
Bapat R.B., 2010, Graphs and Matrices, DOI [ 10.1007/978-1-84882-981-7, DOI 10.1007/978-1-84882-981-7]
[3]   Toughness in graphs - A survey [J].
Bauer, D ;
Broersma, H ;
Schmeichel, E .
GRAPHS AND COMBINATORICS, 2006, 22 (01) :1-35
[4]  
Bondy JA., 1976, GRAPH THEORY APPL, DOI DOI 10.1007/978-1-349-03521-2
[5]  
Brouwer AE, 2012, UNIVERSITEXT, P1, DOI 10.1007/978-1-4614-1939-6
[6]  
Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6
[7]   Maximizing the sum of the squares of the degrees of a graph [J].
Das, KC .
DISCRETE MATHEMATICS, 2004, 285 (1-3) :57-66
[8]  
FIEDLER M, 1973, CZECH MATH J, V23, P298
[9]   Remarks on Component Factors [J].
Gao, Wei ;
Wang, Wei-Fan .
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA, 2023, 11 (03) :657-666
[10]   Graph toughness from Laplacian eigenvalues [J].
Gu, Xiaofeng ;
Haemers, Willem H. .
ALGEBRAIC COMBINATORICS, 2022, 5 (01)