A Class of Max-κ Min-n_κ Graphs  

作　　者：李晓明 

出　　处：《Journal of Harbin Institute of Technology(New Series)》1994年第1期34-41,共8页哈尔滨工业大学学报（英文版）

摘　　要：ＡＣｌａｓｓｏｆＭａｘ－κＭｉｎ－ｎ_κＧｒａｐｈｓＬＩＸｉａｏｍｉｎｇ（李晓明）（Ｄｅｐｔ．ｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ．ＨａｒｂｉｎＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ，１５０００１，Ｃｈｉｎ?..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.

关 键 词：ss: Network reliability RELIABLE GRAPHS with NODE failure EXTREMAL GRAPHS 

分 类 号：O157.5[理学—数学]