Search Results for ""

This problem is NP-complete (Garey and Johnson 1983).

The mean distance of a (connected) graph is the mean of the elements of its graph distance matrix. Closed forms for some classes of named graphs are given in the following ...

Call a graph vertex m(a,b,c) a median of a graph G if it lies on all shortest paths between each pair of vertices (a,b), (b,a), and (c,a) in G. A median graph is then defined ...

Polynomials m_k(x;beta,c) which form the Sheffer sequence for g(t) = ((1-c)/(1-ce^t))^beta (1) f(t) = (1-e^t)/(c^(-1)-e^t) (2) and have generating function ...

Let A_n be the set of all sequences that contain all sequences {a_k}_(k=0)^n where a_0=1 and all other a_i=+/-1, and define c_k=sum_(j=0)^(n-k)a_ja_(j+k). Then the merit ...

A minimal dominating set is a dominating set in a graph that is not a proper subset of any other dominating set. Every minimum dominating set is a minimal dominating set, but ...

A minimal vertex cover is an vertex cover of a graph that is not a proper subset of any other vertex cover. A minimal vertex cover corresponds to the complement of maximal ...

A bounded plane convex region symmetric about a lattice point and with area >4 must contain at least three lattice points in the interior. In n dimensions, the theorem can be ...

Polynomials M_k(x) which form the associated Sheffer sequence for f(t)=(e^t-1)/(e^t+1) (1) and have the generating function sum_(k=0)^infty(M_k(x))/(k!)t^k=((1+t)/(1-t))^x. ...

A class of automata similar to cellular automata but which have a single "active" cell instead of updating all cells in parallel. In a mobile automaton, the evolution rules ...