三族新的t-优图及关于t-优图的五个猜想的反例

THREE NEW FAMILIES OF T OPTIMAL GRAPHS AND THE COUNTER EXAMPLES OF FIVE CONJECTURES ON T OPTIMAL GRAPHS

得到了三族新的ｔ优图．反证了Ｂｏｅｓｃｈ等人提出的关于ｔ优图１０个猜想中的５个猜想，并提出４个新的猜想．比如以下的猜想不正确：若Ｇ是ｎ点ｅ边ｔ优图，ｎ＜ｅ＜ｎ（ｎ－１）２，则其连通度是［２ｅｎ］．代之以新的猜想：若Ｇ是ｎ点ｅ边ｔ优图，则其边连通度λ（Ｇ）＝［２ｅｎ］；并且若λ（Ｇ）３。

Let G be a graph with n vertices and e edges and let t(G) denote the number of spanning trees of G. G is called a t optimal graph (TOG) if t(G)t(G′) for all graphs G ′ with n vertices and e edges. TOG have important applications in network reliability and optimal design theory. Except for trees and cycles, only five families of TOG have been known so far. Let P k denote a path with k vertices, C 3 a cycle with 3 vertices, G c the complement of G . In this paper, three new families of TOG are obtained as follows: G 1=(P 3∪n-32P 2) c, G 2=(2P 3∪n-62P 2) c, G 3=(C 3∪n-32P 2) c. F. T. Boesch et al . proposed ten conjectures on TOG in 1991. Five of them are disproved and four new conjectures are proposed in this paper. For example, the following conjecture is not true: If G is a TOG with n vertices and e edges, where n<e<n(n-1)2 , then its connectivity is [2en] . Instead a new conjecture is proposed: If G is a TOG with n vertices and e edges, then its edge connectivity is λ(G)=[2en] ; moreover, if λ(G) 3 ,then an edge set is a λ edge cut set if and only if it is incident to a vertex of degree λ .