Minimum Number of Edges Guaranteeing the Existence of a K1,t\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{1, t}$$\end{document}-Factor in a Graph

被引:0
作者
Shuya Chiba
Yoshimi Egawa
Shinya Fujita
机构
[1] Kumamoto University,Applied Mathematics, Faculty of Advanced Science and Technology
[2] Tokyo University of Science,Department of Applied Mathematics
[3] Yokohama City University,School of Data Science
关键词
-factor; Number of edges; Minimum degree; 05C70;
D O I
10.1007/s00373-023-02616-0
中图分类号
学科分类号
摘要
Let t,  k,  d be integers with 1≤d≤k-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le d \le k - 1$$\end{document} and t≥8d+11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t \ge 8d + 11$$\end{document}, and let n=k(t+1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n = k(t+1)$$\end{document}. We show that if G is a graph of order n such that δ(G)≥d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta (G) \ge d$$\end{document} and |E(G)|≥n2-(d+1)n+dt+12(d2+3d+4)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|E(G)| \ge \left( {\begin{array}{c}n\\ 2\end{array}}\right) - (d + 1)n + dt + \frac{1}{2}(d^{2} + 3d + 4)$$\end{document}, then G has a K1,t\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{1, t}$$\end{document}-factor. We also give a construction showing the sharpness of the condition on |E(G)|.
引用
收藏
相关论文
共 34 条
[1]  
Akiyama J(1985)On the size of graphs with complete factors J. Graph Theory 9 197-201
[2]  
Frankl P(2013)On perfect packings in dense graphs Electron. J. Combin. 20 #57-132
[3]  
Balogh J(1971)Large cycles in graphs Discrete Math. 1 121-2155
[4]  
Kostochka AV(2007)Perfect packings with complete graphs minus an edge Eur. J. Combin. 28 2143-229
[5]  
Treglown A(1962)Remarks on a paper of Pósa Publ. Math. Inst. Hunger. Acad. Sci. 7 227-203
[6]  
Bondy JA(1961)On the minimal number of vertices representing the edges of a graph Publ. Math. Inst. Hungar. Acad. Sci. 6 181-2690
[7]  
Cooley O(2017)A stability version for a theorem of Erdős on nonhamiltonian graphs Discrete Math. 340 2688-193
[8]  
Kühn D(2018)Extensions of a theorem of Erdős on nonhamiltonian graphs J. Graph Theory 89 176-128
[9]  
Osthus D(2002)-factor in a graph J. Graph Theory 39 111-236
[10]  
Erdős P(2015)A multipartite Hajnal–Szemerédi theorem J. Combin. Theory Ser. B 114 187-269