Nonexistence of optimal graphs for all terminal reliability. Issue 2 (1st October 2013)

• Record Type: Journal Article
• Authors: Brown, J. I.; Cox, D.
• Is Part Of: Networks. Volume 63:Issue 2(2014:Mar.)
• Page Start: 146
• Page End: 153
• Publication Date: 2013-10-01
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21530
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Suppose that every edge of a graph <italic>G</italic> (finite and undirected) is independently operational with probability <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3zxs40kf" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:net21530:net21530-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi><mml:mo>∈</mml:mo><mml:mo>[</mml:mo><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mn>1</mml:mn><mml:mo>]</mml:mo></mml:mrow></mml:math></alternatives>. The all terminal reliability of <italic>G</italic> is the probability that all vertices can communicate. It was conjectured that among all graphs with <italic>n</italic> vertices and <italic>m</italic> edges there always exists a most optimal graph, that is, one whose all terminal reliability is at least as large as any other such graph, no matter what the value of <italic>p</italic>. For each <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3zxs40nj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:net21530:net21530-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mn>6</mml:mn></mml:mrow></mml:math></alternatives>, a single value of <italic>m</italic> was found for which the restriction of the conjecture to simple graphs failed, but it remained open as to whether most optimal graphs exist when multiple edges are allowed. We show that in fact for a given <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3zxs40f7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:net21530:net21530-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mn>6</mml:mn></mml:mrow></mml:math></alternatives>, there are several values of <italic>m</italic> for which a most optimal simple graph does not exist. Moreover, we prove that including multiple edges still does not introduce a most optimal graph, disproving for the first time the conjecture for general graphs. In contrast, it will be shown that for a given <italic>n</italic> and <italic>m</italic>, there always exists a least optimal graph. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 146–153 2014</p> </abstract>