DocumentCode :
3529414
Title :
Forbidden subgraph and perfect path-matchings
Author :
Yan, Jingzhi ; Hu, Bin ; Zhang, Heping ; Zhu, Tingzhao ; Li, Xiaowei
Author_Institution :
Sch. of Inf. Sci. & Eng., Lanzhou Univ., Lanzhou, China
fYear :
2009
fDate :
23-24 Aug. 2009
Firstpage :
86
Lastpage :
89
Abstract :
As a common generalization of matchings and matroid intersection, Cunningham and Geelen introduced the notion of path-matchings in 1996. Let K1,t denote the star with t + 1 vertices. A graph is K1. t-free if G contains no K1, t, as its induced subgraph. Sumner showed that (t - 1)-connected K1, t-free graphs with even number of vertices have a perfect matching. In this paper, some sufficient conditions for the existence of perfect path-matching of K1, t-free graphs are presented. As an immediate consequence, we improve Sumner´s result.
Keywords :
graph theory; forbidden subgraph; matroid intersection; path-matching; Decision support systems;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Web Society, 2009. SWS '09. 1st IEEE Symposium on
Conference_Location :
Lanzhou
Print_ISBN :
978-1-4244-4157-0
Electronic_ISBN :
978-1-4244-4158-7
Type :
conf
DOI :
10.1109/SWS.2009.5271774
Filename :
5271774
Link To Document :
بازگشت