On Tight Components and Anti-Tight Components

Abstract

A graph $$G=(V,E)$$ is called factor-critical if $$G\ne \emptyset $$ and $$G-v$$ has a perfect matching for every vertex $$v\in V(G)$$ . A factor-critical graph $$G$$ is tight (anti-tight, respectively) if for any $$v\in V(G)$$ , any perfect matching $$M$$ in $$G-v$$ , and any $$e\in M$$ , $$|N(v)\cap V(e)|\ne 1$$ ( $$|N(v)\cap V(e)|\ne 2$$ , respectively), where $$N(v)$$ denotes the neighborhood of $$v$$ and $$V(e)$$ denotes the set of vertices incident with $$e$$ . A graph $$G$$ is minimally anti-tight if $$G$$ is anti-tight but $$G-e$$ is not anti-tight for every $$e\in E(G)$$ . In this paper, we prove that a connected graph is tight iff every block of the graph is an odd clique, and that every minimally anti-tight graph is triangle-free.