Matching (graph theory)In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem. Given a graph G = (V, E), a matching M in G is a set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share common vertices.
Matching in hypergraphsIn graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph. Recall that a hypergraph H is a pair (V, E), where V is a set of vertices and E is a set of subsets of V called hyperedges. Each hyperedge may contain one or more vertices. A matching in H is a subset M of E, such that every two hyperedges e_1 and e_2 in M have an empty intersection (have no vertex in common).
Bipartite double coverIn graph theory, the bipartite double cover of an undirected graph G is a bipartite, covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs, G × K_2. It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of G. It should not be confused with a cycle double cover of a graph, a family of cycles that includes each edge twice. The bipartite double cover of G has two vertices u_i and w_i for each vertex v_i of G.
Graph homomorphismIn the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices. Homomorphisms generalize various notions of graph colorings and allow the expression of an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems.
Factor-critical graphIn graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) is a graph with n vertices in which every subgraph of n − 1 vertices has a perfect matching. (A perfect matching in a graph is a subset of its edges with the property that each of its vertices is the endpoint of exactly one of the edges in the subset.) A matching that covers 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.
Vertex cover in hypergraphsIn graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph. An equivalent term is a hitting set: given a collection of sets, a set which intersects all sets in the collection in at least one element is called a hitting set. The equivalence can be seen by mapping the sets in the collection onto hyperedges. Another equivalent term, used more in a combinatorial context, is transversal.
Girth (graph theory)In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (that is, it is a forest), its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free. Cage (graph theory) A cubic graph (all vertices have degree three) of girth g that is as small as possible is known as a g-cage (or as a (3,g)-cage).
Clique (graph theory)In the mathematical area of graph theory, a clique (ˈkliːk or ˈklɪk) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.
Hall-type theorems for hypergraphsIn the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others. Hall's marriage theorem provides a condition guaranteeing that a bipartite graph (X + Y, E) admits a perfect matching, or - more generally - a matching that saturates all vertices of Y. The condition involves the number of neighbors of subsets of Y.
MycielskianIn the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of . The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number. Let the n vertices of the given graph G be v1, v2, . . . , vn.
