Model: In a graph, every vertex is always working, but each edge is independently operational with probability p. If G is undirected and an operational state is one taht connects all the vertices, then the probability of the operational edges forming an operational state for the network is the all terminal reliability of the network.

All terminal reliability and computational algebra

Calculating all terminal reliability is #P-complete. Thus we look at efficient ways to approximate all terminal reliability.

The all-terminal reliability of an undirected graph G can be written as

p^n-1(H_{0 +} H₁(1-p) + H₂(1-p)² + ... + H_m-n+1(1-p)^m-n+1 )

where the H_i has some interpretations. Each has import on the problem of estimating all terminal reliability:

After modeling a graph by a ring, one can use Buchberger's algebraic algorithm to find a multicomplex (a set of multisets on a set, closed under multiset containment) where H_i counts the number of sets of size i in the multicomplex. Understanding more about the multicomplex will give stronger bounds for all terminal reliability.

Strongly-connected reliability:

Given a directed graph, what is the probability that all vertices can communicate? Very little work has been done in this case for good reason (it is very difficult!). Again, we look for efficient ways to approximate the strongly-connected reliability:

We have what appears to be some very good bounds in some cases:

There are ways to write a proof that a graph is not 3-colourable (there are 3 possible ways to go to another line of the proof, starting from a complete graph on 4 points: add edges or vertices, identify nonadjacent vertices and a special "Hajos" construction).

As 3-colourability is not likely in co-NP, some proofs should be long. How do we find one? Best that is known that a graph of order n has a proof that is at least O(n²) long.

Can graphs be used to model composing popular music, both harmony and melody? Can such models capture a musical style? Can randomness be introduced to generate compositions (in real time!) that have structure and interest? Is there a way to authenticate music - who likely wrote a piece of music?

We can model the access points for a wireless network as a sphere covering problem. The problem can also be viewed as maximizing the number of vertices dominated by a set of k points in certain types of geometric graphs. What are the best algorithms for doing so?