Search Results for ""

A graph G is hypohamiltonian if G is nonhamiltonian, but G-v is Hamiltonian for every v in V (Bondy and Murty 1976, p. 61). The Petersen graph, which has ten nodes, is the ...

A graph G is distance transitive if its automorphism group is transitive on pairs of vertices at each pairwise distance in the graph. Distance-transitivity is a ...

A graph G having chromatic number gamma(G)=k is called a k-chromatic graph (Harary 1994, p. 127). In contrast, a graph having gamma(G)<=k is said to be a k-colorable graph. A ...

The Kittell graph is a planar graph on 23 nodes and 63 edges that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof of ...

Vizing's theorem states that a graph can be edge-colored in either Delta or Delta+1 colors, where Delta is the maximum vertex degree of the graph. A graph with edge chromatic ...

The Hamming graph H(d,q), sometimes also denoted q^d, is the graph Cartesian product of d copies of the complete graph K_q. H(d,q) therefore has q^d vertices. H(d,q) has ...

The number of inward directed graph edges from a given graph vertex in a directed graph.

A labeled graph G=(V,E) is a finite series of graph vertices V with a set of graph edges E of 2-subsets of V. Given a graph vertex set V_n={1,2,...,n}, the number of ...

An antimagic graph is a graph with e graph edges labeled with distinct elements {1,2,...,e} so that the sum of the graph edge labels at each graph vertex differ.

A maximally nonhamiltonian graph is a nonhamiltonian graph G for which G+e is Hamiltonian for each edge e in the graph complement of G^_, i.e., every two nonadjacent vertices ...