Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin g...Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin graph G=T∪C is IM-extendable if and only if its characteristic tree T is isomorphic to K_(1,3),K_(1,5),K_(1,7) or S_(2,2).展开更多
A graph G is induced matching extendable if every induced matching of G is included in a perfect matching of G. A graph G is generalized induced matching extendable if every induced matching of G is included in a maxi...A graph G is induced matching extendable if every induced matching of G is included in a perfect matching of G. A graph G is generalized induced matching extendable if every induced matching of G is included in a maximum matching of G. A graph G is claw-free, if G dose not contain any induced subgraph isomorphic to K1,3. The k-th power of G, denoted by Gu, is the graph with vertex set V（G） in which two vertices are adjacent if and only if the distance between them is at most k in G. In this paper we show that, if the maximum matchings of G and G3 have the same cardinality, then G3 is generalized induced matching extendable. We also show that this result is best possible. As a result, we show that if G is a connected claw-flee graph, then G3 is generalized induced matching extendable.展开更多
基金Supported by the National Natural Science Foundation of China(Grant Nos.61702291,11801371)Key Research Project in Universities of Henan Province(Grant No.21B110004)。
文摘Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin graph G=T∪C is IM-extendable if and only if its characteristic tree T is isomorphic to K_(1,3),K_(1,5),K_(1,7) or S_(2,2).
基金Supported by the National Natural Science Foundation of China (Grant Nos. 10601051 90818020)the Natural Science Foundation of Zhejiang Province (Grant No. Y6090472)
文摘A graph G is induced matching extendable if every induced matching of G is included in a perfect matching of G. A graph G is generalized induced matching extendable if every induced matching of G is included in a maximum matching of G. A graph G is claw-free, if G dose not contain any induced subgraph isomorphic to K1,3. The k-th power of G, denoted by Gu, is the graph with vertex set V（G） in which two vertices are adjacent if and only if the distance between them is at most k in G. In this paper we show that, if the maximum matchings of G and G3 have the same cardinality, then G3 is generalized induced matching extendable. We also show that this result is best possible. As a result, we show that if G is a connected claw-flee graph, then G3 is generalized induced matching extendable.
