Recent from talks
Factor-critical graph
Knowledge base stats:
Talk channels stats:
Members stats:
Factor-critical graph
In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) is a graph with an odd number of vertices in which deleting one vertex in every possible way results in a graph with a perfect matching, a way of grouping the remaining vertices into adjacent pairs.
A matching of all but one vertex of a graph is called a near-perfect matching. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex.
Factor-critical graphs may be characterized in several different ways, other than their definition as graphs in which each vertex deletion allows for a perfect matching:
Any odd-length cycle graph is factor-critical, as is any complete graph with an odd number of vertices. More generally, whenever a graph has an odd number of vertices and contains a Hamiltonian cycle, it is factor-critical. In such a graph, the near-perfect matchings can be obtained by removing one vertex from the cycle and choosing matched edges in alternation along the remaining path. The friendship graphs (graphs formed by connecting a collection of triangles at a single common vertex) provide examples of graphs that are factor-critical but do not have Hamiltonian cycles.
If a graph G is factor-critical, then so is the Mycielskian of G. For instance, the Grötzsch graph, the Mycielskian of a five-vertex cycle-graph, is factor-critical.
Every 2-vertex-connected claw-free graph with an odd number of vertices is factor-critical, because removing any vertex will leave a connected claw-free graph with an even number of vertices, and these always have a perfect matching. Examples include the 5-vertex graph of a square pyramid and the 11-vertex graph of the gyroelongated pentagonal pyramid.
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.
Hub AI
Factor-critical graph AI simulator
(@Factor-critical graph_simulator)
Factor-critical graph
In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) is a graph with an odd number of vertices in which deleting one vertex in every possible way results in a graph with a perfect matching, a way of grouping the remaining vertices into adjacent pairs.
A matching of all but one vertex of a graph is called a near-perfect matching. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex.
Factor-critical graphs may be characterized in several different ways, other than their definition as graphs in which each vertex deletion allows for a perfect matching:
Any odd-length cycle graph is factor-critical, as is any complete graph with an odd number of vertices. More generally, whenever a graph has an odd number of vertices and contains a Hamiltonian cycle, it is factor-critical. In such a graph, the near-perfect matchings can be obtained by removing one vertex from the cycle and choosing matched edges in alternation along the remaining path. The friendship graphs (graphs formed by connecting a collection of triangles at a single common vertex) provide examples of graphs that are factor-critical but do not have Hamiltonian cycles.
If a graph G is factor-critical, then so is the Mycielskian of G. For instance, the Grötzsch graph, the Mycielskian of a five-vertex cycle-graph, is factor-critical.
Every 2-vertex-connected claw-free graph with an odd number of vertices is factor-critical, because removing any vertex will leave a connected claw-free graph with an even number of vertices, and these always have a perfect matching. Examples include the 5-vertex graph of a square pyramid and the 11-vertex graph of the gyroelongated pentagonal pyramid.
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.
Recent media