Search Results for ""

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

Every planar graph (i.e., graph with graph genus 0) has an embedding on a torus. In contrast, toroidal graphs are embeddable on the torus, but not in the plane, i.e., they ...

The comparability graph of a partially ordered set P=(X,<=) is the graph with vertex set X for which vertices x and y are adjacent iff either x<=y or y<=x in P.

A graph G is said to be separable if it is either disconnected or can be disconnected by removing one vertex, called articulation. A graph that is not separable is said to be ...

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 n-Andrásfai graph is a circulant graph on 3n-1 nodes whose indices are given by the integers 1, ..., 3n-1 that are congruent to 1 (mod 3). The Andrásfai graphs have graph ...

A regular graph that is edge-transitive but not vertex-transitive is called a semisymmetric graph (Marušič and Potočnik 2001). In contrast, any graph that is both ...

The n-crown graph for an integer n>=3 is the graph with vertex set {x_0,x_1,...,x_(n-1),y_0,y_1,...,y_(n-1)} (1) and edge set {(x_i,y_j):0<=i,j<=n-1,i!=j}. (2) It is ...

Given a planar graph G, a geometric dual graph and combinatorial dual graph can be defined. Whitney showed that these are equivalent (Harary 1994), so that one may speak of ...

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