Search Results for ""

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

Let G be a group, and let S subset= G be a set of group elements such that the identity element I not in S. The Cayley graph associated with (G,S) is then defined as the ...

The chromatic invariant theta(G) of a connected graph G is the number of spanning trees of G that have internal activity 1 and external activity 0. For graphs other than the ...

The Harary index of a graph G on n vertices was defined by Plavšić et al. (1993) as H(G)=1/2sum_(i=1)^nsum_(j=1)^n(RD)_(ij), (1) where (RD)_(ij)={D_(ij)^(-1) if i!=j; 0 if ...

As proposed by Hosoya (1971), the Hosoya index (also called Z-index) of a graph is defined by Z = sum_(k=0)^(n)|a_k| (1) = sum_(k=0)^(n)b_k, (2) where n is the number of ...

The (upper) vertex independence number of a graph, often called simply "the" independence number, is the cardinality of the largest independent vertex set, i.e., the size of ...

The Kirchhoff index Kf, also simply called the resistance and denoted R (Lukovits et al. 1999), of a connected graph G on n nodes is defined by ...

The molecular topological index is a graph index defined by MTI=sum_(i=1)^nE_i, where E_i are the components of the vector E=(A+D)d, with A the adjacency matrix, D the graph ...

The term "snark" was first popularized by Gardner (1976) as a class of minimal cubic graphs with edge chromatic number 4 and certain connectivity requirements. (By Vizing's ...

A spanning tree of a graph on n vertices is a subset of n-1 edges that form a tree (Skiena 1990, p. 227). For example, the spanning trees of the cycle graph C_4, diamond ...