Search Results for ""

An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite. A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is ...

The girth of a graphs is the length of one of its (if any) shortest graph cycles. Acyclic graphs are considered to have infinite girth (Skiena 1990, p. 191). The girth of a ...

A graceful labeling (or graceful numbering) is a special graph labeling of a graph on m edges in which the nodes are labeled with a subset of distinct nonnegative integers ...

The (26,8)-Paulus graph having the largest possible graph automorphism group order of all 26-node Paulus graphs (namely 120) is sometimes known as the ...

Petersen's theorem states that every cubic graph with no bridges has a perfect matching (Petersen 1891; Frink 1926; König 1936; Skiena 1990, p. 244). In fact, this theorem ...

The doubly truncated Witt graph is the graph on 330 vertices related to a 3-(22,8,12) design (Brouwer et al. 1989, p. 367). The doubly truncated Witt graph can be constructed ...

A noncayley graph is a graph which is not a Cayley graph. All graphs that are not vertex-transitive are noncayley graphs. However, some vertex-transitive graph are noncayley. ...

The Hamiltonian number h(n) of a connected graph G is the length of a Hamiltonian walk G. In other words, it is the minimum length of a closed spanning walk in the graph. For ...

A triangle-free graph is a graph containing no graph cycles of length three. A simple graph is triangle-free iff Tr(A^3)=0, where A is the adjacency matrix of the graph and ...

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