Search Results for ""

The Harries-Wong graph is one of the three (3,10)-cage graphs, the other two being the (10,3)-cage known as the Balaban 10-cage and the Harries graph. The Harries-Wong graph ...

The truncated icosahedral graph is the cubic Archimedean graph on 60 nodes and 90 edges that is the skeleton of the truncated icosahedron. It is sometimes known as the ...

A simple graph with n>=3 graph vertices in which each graph vertex has vertex degree >=n/2 has a Hamiltonian cycle.

A nonhamiltonian graph is a graph that is not Hamiltonian. All disconnected graphs are therefore nonhamiltoinian, as are acylic graphs. Classes of connected graphs that are ...

The snub cubical graph is the Archimedean graph on 24 nodes and 60 edges obtained by taking the skeleton of the snub cube. It is a quintic graph, is planar, Hamiltonian, and ...

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

A traceable graph is a graph that possesses a Hamiltonian path. Hamiltonian graphs are therefore traceable, but the converse is not necessarily true. Graphs that are not ...

Let a graph G have graph vertices with vertex degrees d_1<=...<=d_m. If for every i<n/2 we have either d_i>=i+1 or d_(n-i)>=n-i, then the graph is Hamiltonian.

A transposition graph G_n is a graph whose nodes correspond to permutations and edges to permutations that differ by exactly one transposition (Skiena 1990, p. 9, Clark ...

The Robertson graph is the unique (4,5)-cage graph, illustrated above. It has 19 vertices and 38 edges. It has girth 5, diameter 3, chromatic number 3, and is a quartic ...