Search Results for ""

The double graph of a given graph G is constructed by making two copies of G (including the initial edge set of each) and adding edges u_1v_2 and v_1u_2 for every edge uv of ...

An edge cover is a subset of edges defined similarly to the vertex cover (Skiena 1990, p. 219), namely a collection of graph edges such that the union of edge endpoints ...

An encoding is a way of representing a number or expression in terms of another (usually simpler) one. However, multiple expressions can also be encoded as a single ...

A generalization of Turán's theorem to non-complete graphs.

The sum over all external (square) nodes of the lengths of the paths from the root of an extended binary tree to each node. For example, in the tree above, the external path ...

There are two camps of thought on the meaning of general recursive function. One camp considers general recursive functions to be equivalent to the usual recursive functions. ...

Given a planar graph G, its geometric dual G^* is constructed by placing a vertex in each region of G (including the exterior region) and, if two regions have an edge x in ...

The skewness of a graph G is the minimum number of edges whose removal results in a planar graph (Harary 1994, p. 124). The skewness is sometimes denoted mu(G) (Cimikowski ...

The Grassmann graph J_q(n,k) is defined such that the vertices are the k-dimensional subspaces of an n-dimensional finite field of order q and edges correspond to pairs of ...

The Hadwiger conjecture is a generalization of the four-color theorem which states that for any loopless graph G with h(G) the Hadwiger number and chi(G) the chromatic ...