n-extendability of line graphs, power graphs, and total graphs.
Derek Holton, Dingjun Lou, Kevin McAvaney · 1995
A graph G that has a perfect matching is n-extendable if every matching of size n lies in a perfect matching of G. We show that when the connectivity of a line graph, power graph, or total graph is sufficiently large then it is n-extendable. Specifically: if G has even size and is (2n + 1)-edge-connected or (n + 2)-connected, then its line graph is n-extendable; if G has even order and is (n + 1)-connected, then G 2 is n-extendable; if G has even order and is connected, then G 2n+1 is n-extendable; if the total graph T (G) has even order and is (2n + 1)-connected, then T (G) is n-extendable. 1 Introduction and terminology All graphs considered in this paper are finite, undirected, connected and simple. The vertex set and edge set of a graph G are denoted by V (G) and E(G) respectivly. The cardinalities of V (G) and E(G) are called respectively the order and size of G. The line graph L(G) of a graph G is the graph whose vertex set is E(G) and in which two vertices are joined ...