### 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 well-known 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 (from-to) | 123-127 |

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

### Cite this

*Discrete Applied Mathematics*,

*218*, 123-127. https://doi.org/10.1016/j.dam.2016.11.006

}

*Discrete Applied Mathematics*, vol. 218, pp. 123-127. https://doi.org/10.1016/j.dam.2016.11.006

**An infinite family of 2-connected graphs that have reliability factorisations.** / Morgan, Kerri; Chen, Ray.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

T1 - An infinite family of 2-connected graphs that have reliability factorisations

AU - Morgan, Kerri

AU - Chen, Ray

PY - 2017/2/19

Y1 - 2017/2/19

N2 - 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 well-known 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.

AB - 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 well-known 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.

KW - Network reliability

KW - Reliability polynomial

KW - Chromatic polynomial

KW - Tutte polynomial

UR - http://www.scopus.com/inward/record.url?scp=85007575537&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2016.11.006

DO - 10.1016/j.dam.2016.11.006

M3 - Article

VL - 218

SP - 123

EP - 127

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -