Projects per year
Abstract
The reliability polynomial Π (G,p) gives the probability that a graph is connected given each edge may fail independently with probability 1−p. Two graphs are reliability equivalent if they have the same reliability polynomial. It is wellknown that the reliability polynomial can factorise into the reliability polynomials of the blocks of a graph. We give an infinite family of graphs that have no cutvertex but factorise into reliability polynomials of graphs of smaller order.
Brown and Colbourn commented that it was not known if there exist pairs of reliability equivalent graphs with different chromatic numbers. We show that there are infinitely many pairs of reliability equivalent graphs where one graph in each pair has chromatic number 3 and the other graph has chromatic number 4.
Original language  English 

Pages (fromto)  123127 
Number of pages  5 
Journal  Discrete Applied Mathematics 
Volume  218 
DOIs  
Publication status  Published  19 Feb 2017 
Keywords
 Network reliability
 Reliability polynomial
 Chromatic polynomial
 Tutte polynomial
Projects
 1 Finished

An algebraic renaissance for the chromatic polynomial
Farr, G., Delbourgo, D., Morgan, K. J., Cameron, P. J. & Jackson, B.
Australian Research Council (ARC), Monash University
31/05/11 → 31/12/14
Project: Research