On Tight Components and Anti-Tight Components
Changhong Lü, Kan Wang, Xingxing Yu · Graphs and Combinatorics · 2015
A graph $$G=(V,E)$$ is called factor-critical if $$G e \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)| e 1$$ ( $$|N(v)\cap V(e)| e 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.