Search Results for ""

There exists no known P algorithm for graph isomorphism testing, although the problem has also not been shown to be NP-complete. In fact, the problem of identifying ...

The Hochberg-O'Donnell fish graph is the unit-distance graph on 23 nodes and 42 edges illustrated above. It is triangle-free and is the smallest example of a unit-distance ...

A graph G is fully reconstructible in C^d if the graph is determined from its d-dimensional measurement variety. If G is globally rigid in R^d on n>=d+2 vertices, then G is ...

A weakly perfect graph is a graph for which omega(G)=chi(G) (without any requirement that this condition also hold on induced subgraphs, which is required for a graph to be ...

The likelihood of a simple graph is defined by starting with the set S_1={(K_11)}. The following procedure is then iterated to produce a set of graphs G_n of order n. At step ...

A directed strongly regular graph is a simple directed graph with adjacency matrix A such that the span of A, the identity matrix I, and the unit matrix J is closed under ...

A k×m×n hexagonal grid graph is a graph of adjoined hexagons consisting of k hexagons along the horizontal triangular axis, m along the northeast axis, and n along the ...

A generalized Moore graph is a regular graph of degree r where the counts of vertices at each distance d=0, 1, ... from any vertex are 1, r, r(r-1), r(r-1)^2, r(r-1)^3, ..., ...

Chvátal defines the term hole to mean "a chordless cycle of length at least four." The restriction "of length at least four" allows use of the term "hole" regardless of if ...

The skeleton graphs of the Johnson solids are polyhedral graphs. The Johnson skeleton graphs J_3 and J_(63) are minimal unit-distance forbidden graphs. The skeleton of the ...