Line graphs containing 2-factors with bounded number of components

Hong Jian Lai, Liming Xiong, Huiya Yan

科研成果: 期刊稿件文章同行评审

摘要

Let G be a connected simple graph of order n. We use L(G) to denote the line graph of G, where L{G) has the edge set of G as its vertex set and two vertices in L(G) are adjacent if and only if the corresponding two edges in G share a common endvertex. A 2-factor of G is a spanning subgraph H of G such that every vertex in H has degree 2. A lot of results on the components of a 2-factor in G have appeared by studying the conditions on the minimum degree of G. In this paper, instead of studying the minimum degree, we use a different approach and obtain the following: if max{<i(x), d(y)} >-1 holds whenever xy ? E(G) and \U\ > 3, P where U = {v: d(v) < " -1}, p > 0 and u > 0 are integers, then for n sufficiently large relative to p and/i, L(G) has a 2-factor with at most p + 1 components. Moreover, L(G) has a 2-factor with at most p components if \U\ < 1. Especially, it extends a result of [10] saying that if 5(G) >-1, then L(G) has a 2-factor with at most p P components. We also show the graphs satisfying the conditions mentioned above are (p+2)-supereulerian, i.e., they have a spanning even subgraph with at most p+2 components. All results are best possible.

源语言英语
页(从-至)171-179
页数9
期刊Journal of Combinatorial Mathematics and Combinatorial Computing
107
出版状态已出版 - 11月 2018

指纹

探究 'Line graphs containing 2-factors with bounded number of components' 的科研主题。它们共同构成独一无二的指纹。

引用此