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

Kerri Morgan, Ray Chen

    Research output: Contribution to journalArticleResearchpeer-review

    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 languageEnglish
    Pages (from-to)123-127
    Number of pages5
    JournalDiscrete Applied Mathematics
    Volume218
    DOIs
    Publication statusPublished - 19 Feb 2017

    Keywords

    • Network reliability
    • Reliability polynomial
    • Chromatic polynomial
    • Tutte polynomial

    Cite this

    @article{134bab4b92474fe8b3a9d7eefdc17bc6,
    title = "An infinite family of 2-connected graphs that have reliability factorisations",
    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.",
    keywords = "Network reliability, Reliability polynomial, Chromatic polynomial, Tutte polynomial",
    author = "Kerri Morgan and Ray Chen",
    year = "2017",
    month = "2",
    day = "19",
    doi = "10.1016/j.dam.2016.11.006",
    language = "English",
    volume = "218",
    pages = "123--127",
    journal = "Discrete Applied Mathematics",
    issn = "0166-218X",
    publisher = "Elsevier",

    }

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

    In: Discrete Applied Mathematics, Vol. 218, 19.02.2017, p. 123-127.

    Research output: Contribution to journalArticleResearchpeer-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 -