TY - JOUR
T1 - Line graphs containing 2-factors with bounded number of components
AU - Lai, Hong Jian
AU - Xiong, Liming
AU - Yan, Huiya
N1 - Publisher Copyright:
© Charles Babbage Research Centre. All rights reserved.
PY - 2018/11
Y1 - 2018/11
N2 - 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{-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.
AB - 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{-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.
KW - 2-factor
KW - Dominating Eu-lerian subgraph
KW - Fc-supereulerian graph
KW - Line graph
KW - Reduced graph
UR - http://www.scopus.com/inward/record.url?scp=85057136933&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:85057136933
SN - 0835-3026
VL - 107
SP - 171
EP - 179
JO - Journal of Combinatorial Mathematics and Combinatorial Computing
JF - Journal of Combinatorial Mathematics and Combinatorial Computing
ER -