On the synthesis of reliable networks
X. Li · 1987
Synthesis problems of reliable networks are considered in this dissertation. A solution to the two-terminal synthesis problem of reliable networks is given. Specifically, we claim that for given ${\rm e}\sb0\ge1,$ ${\rm n}\sb0\ge0,$ $\lambda\sb0\ge0,$ and a set $\{{\rm s,t}\},$ one can always construct a simple graph G, if it exists, with $\vert$V(G)$\vert$ = ${\rm n}\sb0$ + 2, $\{{\rm s,t}\}\subseteq {\rm V(G)},$ and $\vert$E(G)$\vert$ $\le {\rm e}\sb0,$ such that (1) $\lambda {\rm (G)}\ge\lambda\sb0;$ (2) $\lambda\sb{\rm st}$(G) is maximized under the condition (1); (3) ${\rm m}\sb{\lambda\sb{\rm st}}$ is minimized under the conditions (1) and (2) where $\lambda\sb{\rm st}$(G) is the minimum size of edge set whose removal from G results in nodes s and t being in different components, and ${\rm m}\sb{\lambda\sb{\rm st}}$ is the number of distinct such edge sets. A graph is t-optimal if it has the most number of spanning trees among all the graphs with the same numbers of nodes and edges. T-optimal graphs are not only valuable in the design of reliable networks but also of interest in extremal graph theory. Some of the properties of t-optimal graphs are demonstrated. Known t-optimal graphs are surveyed. Among them, for example, there are regular complete bipartite graphs and the famous Petersen graph. A graph is called a max-$\kappa$ graph if it achieves the maximum connectivity for given numbers of nodes and edges. A max-$\kappa$ graph is called a max-$\kappa$ min-${\rm n}\sb\kappa$ graph if it has the minimum number of node disconnecting sets of order $\kappa$ among all max-$\kappa$ graphs with the same numbers of nodes and edges. The construction of max-$\kappa$ min-${\rm n}\sb\kappa$ graphs is proved for ${\rm n \le e} <$ 3n/2, where n is the number of nodes and e is the number of edges.