Search Results for ""

A well-covered graph is a graph for which every minimal vertex cover has the same size, which is equivalent to every maximal independent vertex set being the same size. It is ...

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

An edge-transitive graph is a graph such that any two edges are equivalent under some element of its automorphism group. More precisely, a graph is edge-transitive if for all ...

The idiosyncratic polynomial is the bivariate graph polynomial defined as the characteristic polynomial in x of A+y(J-I-A), where A is the adjacency matrix, J is the unit ...

A subgraph G^' of a graph G is a graph G^' whose vertex set and edge set are subsets of those of G. If G^' is a subgraph of G, then G is said to be a supergraph of G^' ...

The Bron-Kerbosch algorithm is an efficient method for finding all maximal cliques in a graph.

A cubic vertex-transitive graph is a cubic graph that is vertex transitive. Read and Wilson (1998, pp. 161-163) enumerate all connected cubic vertex-transitive graphs on 34 ...

A bishop graph is a graph formed from possible moves of a bishop chess piece, which may make diagonal moves of any length on a chessboard (or any other board). To form the ...

The edge chromatic number, sometimes also called the chromatic index, of a graph G is fewest number of colors necessary to color each edge of G such that no two edges ...

Every nonplanar graph contains either the utility graph K_(3,3) (i.e., the complete bipartite graph on two sets of three vertices) or the pentatope graph K_5 as a ...