Properties
Factor-critical graphs must always have an odd number of vertices, and must be 2-edge-connected (that is, they cannot have any bridges). However, they are not necessarily 2-vertex-connected; the friendship graphs provide a counterexample. It is not possible for a factor-critical graph to be bipartite, because in a bipartite graph with a near-perfect matching, the only vertices that can be deleted to produce a perfectly matchable graph are the ones on the larger side of the bipartition.
Every 2-vertex-connected factor-critical graph with m edges has at least m different near-perfect matchings, and more generally every factor-critical graph with m edges and c blocks (2-vertex-connected components) has at least m − c + 1 different near-perfect matchings. The graphs for which these bounds are tight may be characterized by having odd ear decompositions of a specific form.
Any connected graph may be transformed into a factor-critical graph by contracting sufficiently many of its edges. The minimal sets of edges that need to be contracted to make a given graph G factor-critical form the bases of a matroid, a fact that implies that a greedy algorithm may be used to find the minimum weight set of edges to contract to make a graph factor-critical, in polynomial time.
Read more about this topic: Factor-critical Graph
Famous quotes containing the word properties:
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)