Matchings Defined by Local Conditions

Abstract

A graph has the neighbour-closed-co-neighbour, or ncc property, if for each of its vertices $x$, the subgraph induced by the neighbour set of $x$ is isomorphic to the subgraph induced by the closed non-neighbour set of $x$. Graphs with the ncc property were characterized in [1] by the existence of a locally $C_4$ perfect matching $M$: every two edges of $M$ induce a subgraph isomorphic to $C_4$. In the present article, we investigate variants of locally $C_4$ perfect matchings. We consider the cases where pairs of distinct edges of the matching induce isomorphism types including $P_4$, the paw, or the diamond. We give several characterizations of graphs with such matchings. In addition, we supply characterizations of graphs with matchings whose edges satisfy a prescribed parity condition.