Search Results for ""

The degree of a graph vertex v of a graph G is the number of graph edges which touch v. The vertex degrees are illustrated above for a random graph. The vertex degree is also ...

The clique polynomial C_G(x) for the graph G is defined as the polynomial C_G(x)=1+sum_(k=1)^(omega(G))c_kx^k, (1) where omega(G) is the clique number of G, the coefficient ...

The Petersen family of graphs, not to be confused with generalized Petersen graphs, are a set of seven graphs obtained from the Petersen graph (or complete graph K_6) by del ...

Let a graph G=(V,E) be defined on vertex set V and edge set E. Then a construction sequence (or c-sequence) for G is a linear order on V union E in which each edge appears ...

A Möbius ladder, sometimes called a Möbius wheel (Jakobson and Rivin 1999), of order n is a simple graph obtained by introducing a twist in a prism graph of order n that is ...

A special graph vertex that is designated to turn a tree into a rooted tree or a graph into a rooted graph. The root is sometimes also called "eve," or an "endpoint" (Saaty ...

The rank polynomial R(x,y) of a general graph G is the function defined by R(x,y)=sum_(S subset= E(G))x^(r(S))y^(s(S)), (1) where the sum is taken over all subgraphs (i.e., ...

Let G_1, G_2, ..., G_t be a t-graph edge coloring of the complete graph K_n, where for each i=1, 2, ..., t, G_i is the spanning subgraph of K_n consisting of all graph edges ...

A k-matching in a graph G is a set of k edges, no two of which have a vertex in common (i.e., an independent edge set of size k). Let Phi_k be the number of k-matchings in ...

Let G be a graph, and suppose each edge of G is independently deleted with fixed probability 0<=p<=1. Then the probability that no connected component of G is disconnected as ...