Search Results for ""

The maximal irredundance polynomial R_G(x) for the graph G may be defined as the polynomial R_G(x)=sum_(k=ir(G))^(IR(G))r_kx^k, where ir(G) is the (lower) irredundance ...

The maximal matching-generating polynomial M_G(x) for the graph G may be defined as the polynomial M_G(x)=sum_(k=nu_L(G))^(nu(G))m_kx^k, where nu_L(G) is the lower matching ...

A minimum dominating set is a dominating set of smallest size in a given graph. The size of a minimum dominating set is known as the domination number of the graph. A minimum ...

A topological sort is a permutation p of the vertices of a graph such that an edge {i,j} implies that i appears before j in p (Skiena 1990, p. 208). Only acyclic digraphs can ...

An example of a subspace of the Euclidean plane that is connected but not pathwise-connected with respect to the relative topology. It is formed by the ray y=0, x<=0 and the ...

The transitive reduction of a binary relation R on a set X is the minimum relation R^' on X with the same transitive closure as R. Thus aR^'b for any elements a and b of X, ...

The pentatope is the simplest regular figure in four dimensions, representing the four-dimensional analog of the solid tetrahedron. It is also called the 5-cell, since it ...

The all-pairs shortest path problem is the determination of the shortest graph distances between every pair of vertices in a given graph. The problem can be solved using n ...

An articulation vertex of a connected graph, also called a cut-vertex (Harary 1994, p. 26; West 2000; Gross and Yellen 2006) or "cutpoint" (Harary 1994, p. 26), is a vertex ...

A maximal subgraph of an undirected graph such that any two edges in the subgraph lie on a common simple cycle.