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

详细信息    查看全文

• 作者：Kerri Morgan ; ^{kerri.morgan@monash.edu} ; Rui Chen ^{rui.chen@monash.edu}
• 关键词：Network reliability ; Reliability polynomial ; Chromatic polynomial ; Tutte polynomial
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：19 February 2017
• 年：2017
• 卷：218
• 期：Complete
• 页码：123-127
• 全文大小：416 K
• 卷排序：218

文摘

The reliability polynomial Π(G,p)Π(G,p) gives the probability that a graph is connected given each edge may fail independently with probability 1−p1−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.