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

作　　者：LV ShengMei XIONG LiMing 

机构地区：[1]School of Mathematics and Statistics, Beijing Institute of Technology, Beijing 100081, China [2]School of Mathematics and Statistics, Qinghai University for Nationalities, Xining 810007, China

出　　处：《Science China Mathematics》2017年第1期177-188,共12页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant Nos. 11471037 and 11171129);Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 20131101110048)

摘　　要：We consider even factors with a bounded number of components in the n-times iterated line graphs L^n(G). We present a characterization of a simple graph G such that L^n(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 L^n(G) and also show that the minimum number of components of even factors in L^n(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.We consider even factors with a bounded number of components in the n-times iterated line graphs L^n（G）. We present a characterization of a simple graph G such that L^n（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 L^n（G） and also show that the minimum number of components of even factors in L^n（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.

关 键 词：even factor iterated line graph branch closure claw-free graph 

分 类 号：O157.5[理学—数学] O241.6[理学—基础数学]