Maximum even factors of graphs

详细信息    查看全文

• 作者：Fuyuan Chen^a ; ^{chenfuyuan19871010@163.com" class="auth_mail" title="E-mail the corresponding author} ; Genghua Fan^b ; ¹ ; ^{fan@fzu.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Even graph ; Spanning subgraph ; Large even factor ; 2-Factor
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：119
• 期：Complete
• 页码：237-244
• 全文大小：268 K

文摘

A spanning subgraph F of a graph G is called an even factor of G if each vertex of F has even degree at least 2 in F. Kouider and Favaron proved that if a graph G has an even factor, then it has an even factor F   with $|E(F)|\ge \frac{9}{16}(|E(G)|+1)$. In this paper we improve the coefficient $\frac{9}{16}$ to $\frac{4}{7}$, which is best possible. Furthermore, we characterize all the extremal graphs, showing that if $|E(H)|\le \frac{4}{7}(|E(G)|+1)$ for every even factor H of G, then G belongs to a specified class of graphs.