Search Results for ""

There are several theorems known as the "sandwich theorem." In calculus, the squeeze theorem is also sometimes known as the sandwich theorem. In graph theory, the sandwich ...

A self-dual graphs is a graph that is dual to itself. Wheel graphs are self-dual, as are the examples illustrated above. Naturally, the skeleton of a self-dual polyhedron is ...

The shortest path problem seeks to find the shortest path (a.k.a. graph geodesic) connecting two specific vertices (u,v) of a directed or undirected graph. The length of the ...

Let a simple graph G have n vertices, chromatic polynomial P(x), and chromatic number chi. Then P(G) can be written as P(G)=sum_(i=0)^ha_i·(x)_(p-i), where h=n-chi and (x)_k ...

The Soicher graphs are three distance-regular graphs on 5346, 486, and 315 vertices, respectively. The first two are also distance-transitive but the third is not. The second ...

A self-organizing data structure which uses rotations to move any accessed key to the root. This leaves recently accessed nodes near the top of the tree, making them very ...

A stack polyomino is a self-avoiding convex polyomino containing two adjacent corners of its minimal bounding rectangle. The number of stack polyominoes with perimeter 2n+4 ...

The number of staircase walks on a grid with m horizontal lines and n vertical lines is given by (m+n; m)=((m+n)!)/(m!n!) (Vilenkin 1971, Mohanty 1979, Narayana 1979, Finch ...

A graph is strongly perfect if every induced subgraph H has an independent vertex set meeting all maximal cliques of H (Berge and Duchet 1984, Ravindra 1999). Every strongly ...

A matrix for a round-robin tournament involving n players competing in n(n-1)/2 matches (no ties allowed) having entries a_(ij)={1 if player i defeats player j; -1 if player ...