Line graphs containing 2-factors with bounded number of components

Hong Jian Lai, Liming Xiong, Huiya Yan

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)171-179
Number of pages9
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
Volume107
Publication statusPublished - Nov 2018

Keywords

  • 2-factor
  • Dominating Eu-lerian subgraph
  • Fc-supereulerian graph
  • Line graph
  • Reduced graph

Fingerprint

Dive into the research topics of 'Line graphs containing 2-factors with bounded number of components'. Together they form a unique fingerprint.

Cite this