Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903044 | Discrete Mathematics | 2018 | 11 Pages |
Abstract
A graph G is induced matching extendable or IM-extendable if every induced matching of G is contained in a perfect matching of G. In 1998, Yuan proved that a connected IM-extendable graph on 2n vertices has at least 3nâ2 edges, and that the only IM-extendable graph with 2n vertices and 3nâ2 edges is TÃK2 , where T is an arbitrary tree on n vertices. In 2005, Zhou and Yuan proved that the only IM-extendable graph with 2nâ¥6 vertices and 3nâ1 edges is TÃK2+e, where T is an arbitrary tree on n vertices and e is an edge connecting two vertices that lie in different copies of T and have distance 3 between them in TÃK2. In this paper, we introduced the definition of Q-joint graph and characterized the connected IM-extendable graphs with 2nâ¥4 vertices and 3n edges.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ju Zhou,