摘要
ＡＣｌａｓｓｏｆＭａｘ－κＭｉｎ－ｎ_κＧｒａｐｈｓＬＩＸｉａｏｍｉｎｇ（李晓明）（Ｄｅｐｔ．ｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ．ＨａｒｂｉｎＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ，１５０００１，Ｃｈｉｎ?..
A graph is called max-κ if it achieves the maximum connectivity for given numbers of nodes and edges. A max-κ graph is said to be max-κ min-nκ if it has the minimum number of node disconnnecting sets of order κ among all max-κ graphs in the same class. The notion of max-λ min-mλ graphs is defined analogously for edge conncetivity. Max-κ min-nκ.(max-λ min-mλ) graphs are proved to be reliable with respect to node(edge) failure when failure probability associated with each node(edge) is small[2,5]. Bauer, Boesch, Suffel, and Tindell have constructed max-λ min-mλ graphs for any given n and e with n-1≤e≤n(n-1)/2 in [3].A general solution to the problem of constructing max-κ min-nκgraphs has not been discovered yet. In this work, we shall show that the construction of max-λ min-mλ graphs for n≤e≤3n/2 proposed by the authors of [3] also generates all max-κ min-nκ graphs in that range except for 6≤n≤7 and e=n+2.
