Even factors with a bounded number of components in iterated line graphs

Sheng Mei Lv, Li Ming Xiong*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We consider even factors with a bounded number of components in the n-times iterated line graphs Ln(G). We present a characterization of a simple graph G such that Ln(G) has an even factor with at most k components, based on the existence of a certain type of subgraphs in G. Moreover, we use this result to give some upper bounds for the minimum number of components of even factors in Ln(G) and also show that the minimum number of components of even factors in Ln(G) is stable under the closure operation on a claw-free graph G, which extends some known results. Our results show that it seems to be NP-hard to determine the minimum number of components of even factors of iterated line graphs. We also propose some problems for further research.

Original languageEnglish
Pages (from-to)177-188
Number of pages12
JournalScience China Mathematics
Volume60
Issue number1
DOIs
Publication statusPublished - 1 Jan 2017

Keywords

  • branch
  • claw-free graph
  • closure
  • even factor
  • iterated line graph

Fingerprint

Dive into the research topics of 'Even factors with a bounded number of components in iterated line graphs'. Together they form a unique fingerprint.

Cite this