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

详细信息    查看全文

• 作者：ShengMei Lv ; LiMing Xiong
• 关键词：even factor ; iterated line graph ; branch ; closure ; claw ; free graph
• 刊名：Science China Mathematics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：60
• 期：1
• 页码：177-188
• 全文大小：253KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Applications of Mathematics;
• 出版者：Science China Press
• ISSN：1869-1862
• 卷排序：60

文摘

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.