Even factors of graphs

被引:0
作者
Jian Cheng
Cun-Quan Zhang
Bao-Xuan Zhu
机构
[1] West Virginia University,Department of Mathematics
[2] Jiangsu Normal University,School of Mathematics and Statistics
来源
Journal of Combinatorial Optimization | 2017年 / 33卷
关键词
Spanning subgraph; Maximum even factor; 2-Factor; Extremal graph theory;
D O I
暂无
中图分类号
学科分类号
摘要
An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Favaron and Kouider (J Gr Theory 77:58–67, 2014) showed that if a simple graph G has an even factor, then it has an even factor F with |E(F)|≥716(|E(G)|+1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|E(F)| \ge \frac{7}{16} (|E(G)| + 1)$$\end{document}. This ratio was improved to 47\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{4}{7}$$\end{document} recently by  Chen and Fan (J Comb Theory Ser B 119:237–244, 2016), which is the best possible. In this paper, we take the set of vertices of degree 2 (say V2(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V_{2}(G)$$\end{document}) into consideration and further strengthen this lower bound. Our main result is to show that for any simple graph G having an even factor, G has an even factor F with |E(F)|≥47(|E(G)|+1)+17|V2(G)|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|E(F)| \ge \frac{4}{7} (|E(G)| + 1)+\frac{1}{7}|V_{2}(G)|$$\end{document}.
引用
收藏
页码:1343 / 1353
页数:10
相关论文
共 8 条
[1]  
Chen F(2016)Maximum even factors of graphs J Comb Theory Ser B 119 237-244
[2]  
Fan G(1965)Maximum matching and a polyhedron with 0, 1-vertices J Res Natl Bur Stand Sect B 69 125-130
[3]  
Edmonds J(2014)Even factors of large size J Gr Theory 77 58-67
[4]  
Favaron O(1976)Eine gemeinsame Basis für die Theorie der eulerschen Graphen und den Satz von Petersen Monatsh Math 81 267-278
[5]  
Kouider M(1992)Spanning Eulerian subgraph, the splitting lemma and Petersen’s theorem Discrete Math 101 3-37
[6]  
Fleischner H(1891)Die Theorie der regulären graphs Acta Math 15 193-220
[7]  
Fleischner H(undefined)undefined undefined undefined undefined-undefined
[8]  
Petersen J(undefined)undefined undefined undefined undefined-undefined