Search Results for ""

Let (Omega)_(ij) be the resistance distance matrix of a connected graph G on n nodes. Then Foster's theorems state that sum_((i,j) in E(G)))Omega_(ij)=n-1, where E(g) is the ...

The König-Egeváry theorem, sometimes simply called König's theorem, asserts that the matching number (i.e., size of a maximum independent edge set) is equal to the vertex ...

The vertical line test is a graphical method of determining whether a curve in the plane represents the graph of a function by visually examining the number of intersections ...

The blossom algorithm (Edmonds 1965) finds a maximum independent edge set in a (possibly weighted) graph. While a maximum independent edge set can be found fairly easily for ...

The Császár polyhedron is a polyhedron that is topologically equivalent to a torus which was discovered in the late 1940s by Ákos Császár (Gardner 1975). It has 7 polyhedron ...

An acyclic digraph is a directed graph containing no directed cycles, also known as a directed acyclic graph or a "DAG." Every finite acyclic digraph has at least one node of ...

Dirac (1952) proved that if the minimum vertex degree delta(G)>=n/2 for a graph G on n>=3 nodes, then G contains a Hamiltonian cycle (Bollobás 1978, Komlós et al. 1996). In ...

Given a weighted, undirected graph G=(V,E) and a graphical partition of V into two sets A and B, the cut of G with respect to A and B is defined as cut(A,B)=sum_(i in A,j in ...

The word "rank" refers to several related concepts in mathematics involving graphs, groups, matrices, quadratic forms, sequences, set theory, statistics, and tensors. In ...

The blow-up lemma essentially says that regular pairs in Szemerédi's regularity lemma behave like complete bipartite graphs from the point of view of embedding bounded degree ...