A Simple Proof of the Gross-Saccoman Multigraph Conjecture
An enigmatic conjecture in network synthesis asserts that the the uniformly most reliable multigraphs are simple. Daniel Gross and John Saccoman proved in 1998 that the answer is affirmative whenever m ≤ n + 2, where n and m is the respective number of nodes and edges of the multigraphs. They conjec...
সংরক্ষণ করুন:
| প্রধান লেখক: | |
|---|---|
| অন্যান্য লেখক: | , |
| বিন্যাস: | article |
| ভাষা: | ইংরেজি |
| প্রকাশিত: |
2022
|
| বিষয়গুলি: | |
| অনলাইন ব্যবহার করুন: | https://hdl.handle.net/20.500.12381/701 |
| ট্যাগগুলো: |
কোনো ট্যাগ নেই, প্রথমজন হিসাবে ট্যাগ করুন!
|
| সংক্ষিপ্ত: | An enigmatic conjecture in network synthesis asserts that the the uniformly most reliable multigraphs are simple. Daniel Gross and John Saccoman proved in 1998 that the answer is affirmative whenever m ≤ n + 2, where n and m is the respective number of nodes and edges of the multigraphs. They conjectured that the optimality is also achieved by simple graphs when m = n + 3. A proof for this conjecture recently appeared. In this article we provide a unified short proof for the previous cases where m ≤ n + 3. Our proof strategy holds whenever the most reliable simple graphs satisfy the self similarity property. As a consequence, it could be used to study the general multigraph conjecture for larger graph classes. |
|---|