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
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;
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
DOI :
10.1109/SWS.2009.5271774