Graph properties

This is another index, which was independently developed by Polansky 46) for expressing some graph properties, including the relation with the Wiener index for important classes of molecular graphs, and by Bonchev, Balaban and Mekenyan 47)... 

Kireev, D.B. (1995). ChemNet A Novel Neural Network Based Method for Graph/Property Mapping. J. Chem.lnf.Comput.Sci., 35,175-180. 

The counting polynomial is a description of a graph property in terms of a sequence of numbers, such as the distance degree sequence or the sequence of the number of k independent edge sets [Hosoya, 1988,1990 Trinajstic, 1992 Diudea, Gutman et al., 2001 Noy, 2003 Diudea, Vizitiu et al., 2007]. The counting polynomial is defined as... 

Many of Cleveland s guidelines are common sense, but when has that ever stopped someone from making a graph. Cleveland used extensive scientific research to determine what graph properties lead to efficient transfer of information to the reader. 

As shown in the examples above we can color the graph components according to the graph properties. In our purine model we could also color the species nodes according to some metadata, such as the phosphorylated state of the proteins or their presence or absence at time t. 

Note that the current domain of a DD is a graph property that is kept at the user level - it is not part of the graph representation. 

Naturally, the examples are endless, and easy to make up. One instance, which has appeared in knot theory, comes from the graph property of being disconnected. It can be shown that the complex of disconnected graphs on n vertices is homotopy equivalent to the order complex of the partition lattice iT see Proposition 13.15. 

Definition 13.1. A graph property is called monotone if the set of graphs that satisfy this property is closed under removal of edges. 

Examples of monotone properties include planarity and the property of being disconnected. The condition in Definition 13.1 is basically the same condition as the one defining abstract simplicial complexes. In fact, the following is the standard construction associating an abstract simphcial complex to a monotone graph property. 

Definition 13.2. Given a monotone graph property Q of graphs with n vertices, the abstract simplicial complex A Q) has ( ) vertices labeled by ordered... 

A graph property is called trivial if either no graphs with n vertices satisfy it, in which case A Q) is void, or all graphs with n vertices satisfy it, in which case A Q) is an (n — l)-dimensional simplex. 

Let us now consider the following algorithmic situation. We are given a certain graph property Q, which we know, and a certain graph G, which we do not know. However, we can ask an oracle questions of the type... 

Our task is to decide whether graph G satisfies the property Q. We would like to ask as few questions as possible. More precisely, we are interested in knowing how many questions we have to ask in the worst-case scenario. For example, if the graph property is trivial, then we do not need to ask any questions at all. On the other hand, if the property is being a complete graph, then we might be forced into asking (2) questions. This would happen if the answers to the first (2) — 1 questions were all positive. 

Definition 13.3. A graph property Q of graphs onn vertices is called evasive if in the worst case we need to ask (2) questions in the course of the algorithm described above. Otherwise, the graph property is called nonevasive. 

By a simple induction on the number of vertices, it will follow that if Q is a nonevasive graph property, then the abstract simplicial complex A Q) is collapsible see Proposition 13.7 and Proposition 13.9. 

It is not all too trivial to construct nonevasive graph properties. One example of such a property is being a so-called scorpion graph. Here a graph G on n vertices is called scorpion if it has 3 vertices s, t, and b such that... 

Since the total number of queries is linear in the number of vertices, we see that for sufficiently large n we will need substantially fewer than (2) questions. In particular, this graph property is nonevasive. 

Every nontrivial monotone graph property for graphs on n vertices is evasive. 

Assume now that n = p, for some prime number p. Assume that the Evasiveness Conjecture is false for that value of n, and let Q denote a monotone, but nonevasive, graph property. Furthermore, let GF(n) denote a field with n elements, which exists because n is a prime power, and let GF(n) denote the multiplicative group of that field. Let F be a subgroup of [Pg.228]

Since the graph property Q is nonevasive, we know that the abstract simplicial complex A Q) is collapsible see Proposition 13.7(2). In particular, it has to be Zp-acyclic. We can now use Theorem 13.5 to conclude that x A Q)r) = 1- On the other hand, the group F acts doubly transitively on the set [n], i.e., any ordered pair of points can mapped to any other ordered pair of points by a transformation from F. This means that the group F acts transitively on the set of vertices of the abstract simplicial complex A Q). Therefore, the only point of A G) that can possibly be fixed by every element in F is the barycenter of the simplex on all (") vertices, which of course can be the case only when A(Q) is a full simplex. This contradicts our assumption that the graph property Q is nontrivial. ... 

Kireev, D. B. (1995) ChemNet a novel neural network-based method for graph/ property mapping. J. Chem. Irtf. Comput. Sci. 35,175-80. 

---