On Tight Components and Anti-Tight Components

摘要

A graph G = (V, E) is called factor-critical if G not equal O and G -v has a perfect matching for every vertex v. V(G). A factor-critical graph G is tight (anti-tight, respectively) if for any v. V(G), any perfect matching M in G -v, and any e. M, | N(v) n V(e)| boolean AND= 1 (| N(v) n V(e)| not equal 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. 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.