Search Results for ""

The m×n king graph is a graph with mn vertices in which each vertex represents a square in an m×n chessboard, and each edge corresponds to a legal move by a king. The number ...

The Pell graph Pi_n is the graph defined as follows. Consider n-tuples of (0,1,2) such that maximal blocks of an odd number of 2's are forbidden. Take these as the vertices ...

Given two positive integers n and k, the bipartite Kneser graph H(n,k) is the graph whose two bipartite sets of vertices represent the k-subsets and (n-k)-subsets of ...

The Wagner graph is a name sometimes given to the 4-Möbius ladder (Bondy and Murty 2008, pp. 275-276). The association arises through the theorem of Wagner (1937) that graphs ...

Let (P,B) denote a configuration with v points P={p_1,...,p_v} and b lines ("blocks") B=(B_1,...,B_b). Then the Levi graph L(P,B), also called the incidence graph, of a ...

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

The (m,n)-tadpole graph, also called a dragon graph (Truszczyński 1984) or kite graph (Kim and Park 2006), is the graph obtained by joining a cycle graph C_m to a path graph ...

The composition G=G_1[G_2] of graphs G_1 and G_2 with disjoint point sets V_1 and V_2 and edge sets X_1 and X_2 is the graph with point vertex V_1×V_2 and u=(u_1,u_2) ...

An arc of a graph, sometimes also called a flag, is an ordered pair of adjacent vertices (Godsil and Royle 2001, p. 59), sometimes also called a directed line (Harary 1994, ...

A Turán graph, sometimes called a maximally saturated graph (Zykov 1952, Chao and Novacky 1982), with positive integer parameters n and k is a type of extremal graph on n ...