Search Results for ""

A fullerene is a cubic polyhedral graph having all faces 5- or 6-cycles. Examples include the 20-vertex dodecahedral graph, 24-vertex generalized Petersen graph GP(12,2), ...

Iofinova and Ivanov (1985) showed that there exist exactly five bipartite cubic semisymmetric graphs whose automorphism groups preserves the bipartite parts and acts ...

A graph is a forbidden minor if its presence as a graph minor of a given graph means it is not a member of some family of graphs. More generally, there may be a family of ...

A polynomial Z_G(q,v) in two variables for abstract graphs. A graph with one graph vertex has Z=q. Adding a graph vertex not attached by any graph edges multiplies the Z by ...

The Balaban 11-cage is the unique 11-cage graph, derived via a tree excision from the 12-cage graph by Balaban (1973) and proven unique by McKay and Myrvold in 2003. It is ...

A unit-distance embedding is a graph embedding in which all edges have unit length. A graph possessing a unit-distance embedding in two dimensions is called a unit-distance ...

The distance polynomial is the characteristic polynomial of the graph distance matrix. The following table summarizes distance polynomials for some common classes of graphs. ...

Let G(V,E) be a graph with graph vertices V and graph edges E on n graph vertices without a (k+1)-clique. Then t(n,k)<=((k-1)n^2)/(2k), where t(n,k) is the edge count. (Note ...

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 ...

A graph is a forbidden (vertex-)induced subgraph if its presence as a vertex-induced subgraph of a given graph means it is not a member of some family of graphs. For example, ...