Induced Matching Extendable Graph Powers

摘要

A graph G is called induced matching extendable (shortly, IM-extendable) if every induced matching of G is included in a perfect matching of G. A graph G is called strongly IM-extendable if every spanning supergraph of G is IM-extendable. The k-th power of a graph G, denoted by G k , is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k.