Search Results for ""

A bicubic graph is a bipartite cubic graph. Tutte (1971) conjectured that all 3-connected bicubic graphs are Hamiltonian (the Tutte conjecture), but a number of bicubic ...

The order-n dipole graph D_n is a multigraph consisting of two vertices and n multiple edges joining them. The dipole graph D_2 is a multigraph that can be considered to ...

The square of a graph is defined as its second graph power. The square of any biconnected graph is Hamiltonian (Fleischner 1974, Skiena 1990, p. 231). Mukhopadhyay (1967) has ...

A cubic nonplanar graph is a graph that is both cubic and nonplanar. The following table summarizes some named nonplanar cubic graphs. graph G |V(G)| utility graph 6 Petersen ...

The Fritsch graph is the 9-node planar graph illustrated above that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof ...

The Georges graph, illustrated above, is 50-node graph which is the smallest currently known example of a 3-connected bicubic nonhamiltonian graph. It is implemented in the ...

The term "null graph" is used both to refer to any empty graph and to the empty graph on 0 nodes. Because of the conflicting usage, it is probably best to avoid use of the ...

A graph is said to be H^*-connected if it is either Hamilton-connected or Hamilton-laceable. S. Wagon (pers. comm., May. 20, 2013; Dupuis and Wagon 2014) conjecture that all ...

A prism graph, denoted Y_n, D_n (Gallian 1987), or Pi_n (Hladnik et al. 2002), and sometimes also called a circular ladder graph and denoted CL_n (Gross and Yellen 1999, p. ...

Let a tree S be a subgraph of a cubic graph G. The graph excision G circleminus S is the graph resulting from removing the tree, then merging the edges. For example, if in ...