Search Results for ""

The path covering number (or path-covering number; Slater 1972) of a graph G, variously denoted as summarized below, is the minimum number of vertex-disjoint paths that cover ...

The cycle double cover conjecture states that every bridgeless graph has a collection of cycles which together contain every edge exactly twice. This conjecture remains open, ...

The matrix tree theorem, also called Kirchhoff's matrix-tree theorem (Buekenhout and Parker 1998), states that the number of nonidentical spanning trees of a graph G is equal ...

The detour matrix Delta, sometimes also called the maximum path matrix or maximal topological distances matrix, of a graph is a symmetric matrix whose (i,j)th entry is the ...

What is the probability that a chord drawn at random on a circle of radius r (i.e., circle line picking) has length >=r (or sometimes greater than or equal to the side length ...

The maximum possible weight of a fractional clique of a graph G is called the fractional clique number of G, denoted omega^*(G) (Godsil and Royle 2001, pp. 136-137) or ...

The longest path problem asks to find a path of maximum length in a given graph. The problem is NP-complete, but there exists an efficient dynamic programming solution for ...

The Robertson-Seymour theorem, also called the graph minor theorem, is a generalization of the Kuratowski reduction theorem by Robertson and Seymour, which states that the ...

A sequence whose terms are integers. The most complete printed references for such sequences are Sloane (1973) and its update, Sloane and Plouffe (1995). Neil Sloane ...

A figurate number which is constructed as an octahedral number with a square pyramid removed from each of the six graph vertices, TO_n = O_(3n-2)-6P_(n-1)^((4)) (1) = ...