On Perfect Matchings of Complements of Line Graphs

Abstract

Let \(G = (V(G), E(G))\) be a nonempty graph (may have parallel edges). The line graph \(L(G)\) of \(G\) is the graph with \(V(L(G)) = E(G)\), and in which two vertices \(e\) and \(e’\) are joined by an edge if and only if they have a common vertex in \(G\). We call the complement of \(L(G)\) as the jump graph. In this note, we give a simple sufficient and necessary condition for a jump graph to have a perfect matching.