Забыли?

?

# 97

код для вставкиСкачать
```Maximizing Spanning Trees in Almost Complete
Graphs
Bryan Gilbert, Wendy Myrvold
University of Victoria, P.O. Box 3055, MS 7209, Victoria, BC, Canada V8W 3P6
Received 26 April 1995; accepted 3 September 1996
Abstract: We examine the family of graphs whose complements are a union of paths and cycles and
develop a very simple algebraic technique for comparing the number of spanning trees. With our algebra,
we can obtain a simple proof of a result of Kel’mans that evening out path lengths increases the number
of spanning trees in the complement graph. We provide similar characterizations for cycles. The theorems
that we develop enable us to characterize the graphs in this family with a maximum number of spanning
trees. q 1997 John Wiley & Sons, Inc. Networks 30: 23–30, 1997
1. INTRODUCTION
A graph G consists of a set V (G) of vertices and a
set E(G) of edges where each edge corresponds to an
unordered pair of vertices from V (G). All graphs that
we consider are simple (they have no loops or multiple
edges), finite, and undirected. We use n to denote the
number of vertices of a graph, and m, for the number of
edges. The class of (n, m)-graphs contains all simple
graphs on n vertices and m edges. A spanning tree of a
graph G on n vertices is an acyclic (n 0 1)-edge subgraph. Any undefined graph theoretic terms can be found
in [4].
Given n vertices and m edges, how can you construct
a graph having the maximum number of spanning trees?
This question has applications to network reliability since
under the all-terminal model, graphs with the most trees
give the best topology when the edges are sufficiently
unreliable (pointed out by Kel’mans in [12, p. 2119]).
Correspondence to: W. Myrvold; e-mail: wendym@csr.uvic.ca
Under this model, the vertices are assumed to be perfectly
reliable and edges operate independently at random with
the same probability p. The network is operational if all
the vertices can communicate with each other or, equivalently, if there exists at least one operational spanning tree.
A network is uniformly the best topology under this
model if it is more reliable than any other (n, m)-graph
regardless of the probability of edge operation. Kel’mans
[17] proved that uniformly most reliable graphs do not
always exist, and this was independently rediscovered in
[21]. Colbourn’s monograph [8] provides a nice survey
up to 1987 of the results for all-terminal reliability and
other reliability problems. Boesch’s survey of 1986 [1]
introduces the important principles for uniformly most
reliable networks and summarizes the results up to that
date.
The topologies with a maximum number of trees are
known for very sparse graphs (having up to n / 3 edges).
It has also been proved that these graphs are uniformly
most reliable by Boesch et al. [3] for up to n / 2 edges
and by Wang [27] for n / 3 edges. The best graphs are
summarized in the following table:
q 1997 John Wiley & Sons, Inc.
CCC 0028-3045/97/010023-08
23
8U11
/ 8U11\$\$0766
06-09-97 15:09:59
netwas
W: Networks
766
24
GILBERT AND MYRVOLD
m
õn 0 1
n01
n
n/1
n/2
n/3
Graphs With the Most Trest
Every graph since all have no trees
Any tree
An n-cycle
A u-graph with path lengths as
even as possible
A particular subdivision of K4
(see Fig. 1)
A particular subdivision of K3,3
(see Fig. 2)
Ref.
[28]
[26]
[3]
In a regular complete multipartite graph, the vertices
can be partitioned into sets of equal size so that within a
set no two vertices are adjacent and every two vertices
chosen from two different sets are adjacent. A design
theory result of Cheng [6] when reformulated in graph
theoretic terms [7] gives a proof that regular complete
multipartite graphs maximize the number of trees over
graphs on the same numbers of vertices and edges. It is
not known if these graphs are uniformly most reliable.
The topologies with a maximum number of trees are
also known for very dense graphs (when at most n 0 2
edges are removed from the complete graph). We use Kn
to denote the complete graph on n vertices. The complement GV of a graph G with respect to Kn is the n-vertex
graph containing exactly the edges of Kn which are not
in G. Because the graphs that we consider are close to
being complete, it is often easier to consider the complements.
When the number of edges is at most n/2 less than
that in the complete graph Kn , the best topology is the
graph whose complement consists of a set of independent
Fig. 2. The best graph on n / 3 edges; subdivision of edges
is done in alphabetic order (A, B, C, . . .).
edges. This was proved independently by Kel’mans and
Chelnokov [17] and Shier [24]. It has also been shown
that these graphs are uniformly most reliable by using a
reliability increasing operation called swing surgery [23].
The remaining dense cases were characterized by Petingi
and co-workers [21, 22]. They also characterized the best
graphs when n Å 3k edges are removed (k is an integer)
or when n 0 1 edges are removed and n Å 3k / 2.
In this paper, we developed a very simple algebraic
proof technique for ranking graphs according to the number of trees. The technique is applicable to all graphs
whose complements are a union of paths and cycles (including paths on one vertex, i.e., isolated vertices). Our
theorems permit rankings of these graphs extending beyond that attained by Petingi and co-workers [21, 22].
A graph is almost-regular if the degrees of its vertices
differ by at most one. This implies that the degrees are
all the same if possible or there are only two consecutive
values in the degree sequence. If attention is restricted to
the almost-regular graphs, then we are able to characterize
the graphs with the most trees in all cases where up to n
edges are removed from the complete graph. It remains
to be shown that almost-regularity is a necessity for the
cases which were not covered by Petingi and co-workers
[21, 22].
Section 2 introduces the spanning tree counting formulas that we require. These are used to justify our new
algebraic technique in Section 3. This technique is applied
to rank various classes of graphs according to the number
of trees in Section 4. Then, these theorems are utilized
to characterize the almost-regular graphs with the most
trees in Section 5. Finally, we conclude in Section 6 with
a list of the most promising areas for future research.
The symbolic algebra package MAPLE proved invaluable for creating and checking all of our algebraic results.
2. PATH AND CYCLE FORMULAS
Fig. 1. The best graph on n / 2 edges; subdivision of edges
is done in alphabetic order (A, B, C, . . .).
8U11
/ 8U11\$\$0766
06-09-97 15:09:59
The most common formula used for finding the number
of trees in a graph is the Kirchhoff matrix tree theorem
netwas
W: Networks
766
MAXIMIZING SPANNING TREES IN ALMOST COMPLETE GRAPHS
25
Fig. 3. The complement spanning tree matrix and the complement graph.
[18]. A proof which provides graph theoretic intuition can
be found in Gibbon’s book [10, pp. 49–54]. In this section,
we introduce a formula that is algebraically equivalent, but
more convenient for the graphs that we consider since the
formulation is in terms of the complement of the graph.
Temperley was the first to use this [25].
The complement spanning tree matrix, KV (G), of a
graph G with respect to Kn has ith diagonal entry equal
to n minus the degree of the ith vertex of GV , and offdiagonal entry (i, j) is 1 if ( £i , £j ) is an edge of GV and
0 otherwise. Proofs of this next theorem occur in several
references including [5, p. 39, Theorem 2.5.4].
Theorem 2.1. The number of spanning trees of G, t(G),
is equal to
1
∗ det(KU (G)).
n2
j
As an example to illustrate the concepts just introduced, consider the graph whose complement consists of
two independent edges plus some isolated vertices. The
complement graph and its complement spanning tree matrix are pictured in Figure 3. The determinant of KV (G) is
n n (1 0 2/n) 2 and, hence, the number of trees equals
n n0 2 (1 0 2/n) 2 .
Moon introduced the generic form f (n, G) of a graph
G [20]. It is equal to (1/n n ) ∗ det(KV (GV )). For example,
f (n, G), where G is the graph in Figure 3, is equal to (1
0 2/n) 2 . This leads to the following nice corollary which
shows that to compute the number of trees of a graph we
can consider the components of the complement independently. This corollary has been stated by numerous authors in various guises.
algebra which states that the determinant of a block diagonal matrix is the product of the determinants of the blocks.
If the vertices of the components of GV are given consecutive vertex labels, then in KV (G), each results in a block.
If you divide each row of the complement spanning
tree matrix by n, then the resulting determinant is the
product of the generic forms of the components. Thus,
our corollary is obtained from Theorem 2.1 since dividing
each row of a matrix by n and premultiplying by n n
preserves the value of the determinant.
j
We now give the generic forms for a path on k vertices
(Pk ) and a cycle on k vertices (Ck ) with respect to Kn .
These results are implicit in the work of Kel’mans [12,
13] and can also be found in the technical report of
Boesch and Suffel [2]. Proofs are also given in detail in
Gilbert’s thesis [11, Chap. 4]. To derive these formulas,
the complement spanning tree matrix is used to define a
recurrence which is solved using standard methods.
Theorem 2.3. The generic form f (n, Pk ) for Pk 1 ° k
° n, and n ú 4 is given by
q
1
0
2
/
n 2 0 4n ) k
((n
n 2 0 4n
q
2 kn k0 1
q
0 (n 0 2 0 n 2 0 4n ) k ).
The restriction n ú 4 is not a serious limitation since
it is easy to classify all graphs on four or fewer vertices
with respect to the number of trees that they have.
Theorem 2.4. The generic form f (n, Ck ) for Ck , 3 ° k
° n, and n ¢ 4, is given by
q
1
((n
0
2
/
n 2 0 4n ) k
2 kn k
q
/ (n 0 2 0 n 2 0 4n ) k / ( 02) k/ 1 ).
Corollary 2.2. If the complement of the n-vertex graph G
has k components G1 , G2 , . . . , Gk (or, equivalently, GV
Å G1 / G2 , rrr / Gk ), then t(G) Å n n02 ∏ kiÅ1 f (n, Gi ).
Proof. First recall the elementary result from linear
8U11
/ 8U11\$\$0766
06-09-97 15:09:59
j
j
3. OUR NEW ALGEBRA
In this section, we explain how to simplify the formulas
from the previous section. This culminates in a proof
netwas
W: Networks
766
26
GILBERT AND MYRVOLD
technique that permits short proofs of many interesting
results (given in the next section).
For notational convenience, we define the following
functions of n:
x k f (n, Pk ) Å
1
(x 2 k 0 1)
n k0 1s
and
r å r(n) Å n 0 2
q
x k f (n, Ck ) Å
s å s(n) Å n 2 0 4n
1
1
(x 2 k / 1 / 2dk x k ) Å k (x k / dk ) 2 .
k
n
n
p å p(n) Å r / s
q å q(n) Å r 0 s
x å x(n) Å p/2.
x which is required for all the proofs in the next section.
Lemma 3.1. For n ¢ 5, x ú 2.
4. COMPARATIVE RESULTS
Proof. Clearly, x is an increasing function of n. Also,
x(5) ú 2.
j
For our algebraic proof technique, we define a function
A(G) equal to (x 2 k 0 1) for the path Pk , and (x k / dk ) 2
for the cycle Ck , where dk is 1 if k is odd and 01 if k is
even. We see in the proof of the next theorem a rationale
for defining this function.
Theorem 3.2. If G and H are both graphs whose complements are unions of paths and cycles on n vertices and
m edges, n ¢ 5, then t(G) ú t(H) if and only if
∏
∏
A(C) ú
C is a component of GU
A(C).
C is a component of HU
(Theorem 2.3) and cycles (Theorem 2.4) given in the
previous section. Rewriting using our notation given
above and rearranging so the 2 k is divided into each term
rather than being factored out in front gives
f (n, Pk ) Å
1
n k0 1s
SS D S D D
p
2
It is easy to show that the number l of paths (including
P1’s) of G or H is a constant dependent on m. Also, since
multiplying both spanning tree formulas further by n ms l
preserves the relative ranking, we see that this theorem
is true.
j
k
q
2
0
k
We begin this section with the definition of a partial order
¥ over (n, m)-graphs established by Kel’mans [14, p.
254]. If we consider two graphs G and H with k vertices,
then we define G ¥ H if t(Kn 0 G) ú t(Kn 0 H) for all
n ¢ k.
We point out that ¥ is not a total order. Kel’mans and
Chelnokov gave a complicated example of a pair of
¥-incomparable graphs in [17, p. 211]. Later in a 1980
research announcement, Kel’mans [15] stated, without
details, a number of other examples of ¥-incomparable
graphs. One simple example is as follows: ¥ cannot be
used to order the two 8-vertex graphs G Å P3 / P3 / P1
/ P1 and H Å P4 / K1,3 because t(K8 0 G) Å 40,000
ú t(K8 0 H) Å 39,984 but t(K9 0 G) Å 944,784 õ t(K9
0 H) Å 947,520. Other examples of graphs incomparable
with respect to ¥ include nonisomorphic graphs with
the same number of trees ( cospectral graphs, see [9,
Chap. 6 ] ) .
In this section, we rank some families of graphs according to this operator. First, we consider graphs whose
complements are paths (Section 4.1). The next step is to
consider cycles (Section 4.2). Our final theorems involve
graphs whose complements are a mixture of paths and
cycles (Section 4.3).
and
1
f (n, Ck ) Å k
n
SS D S D
p
2
k
/
q
2
k
4.1. RANKING PATH COMPONENTS
D
/ 2dk .
Multiplying the formulas for t(G) and t(H) given by
Corollary 2.2 by x n preserves the rankings of the two
formulas. Applying x k to each term corresponding to a
Pk or a Ck and observing that pq Å 4, we get
8U11
/ 8U11\$\$0766
06-09-97 15:09:59
In this section, we prove that evening out the lengths of
paths increases the number of spanning trees. This result
is originally due to Kel’mans [14, Lemma 6.8, p. 258]
(note that this paper uses the notation Cn to represent a
path on n vertices).
Theorem 4.1. Let m ¢ 4 (and n ¢ 5), and let
netwas
W: Networks
766
MAXIMIZING SPANNING TREES IN ALMOST COMPLETE GRAPHS
27
which the lengths have the same parity. The second theorem handles the case in which the parities differ.
G(c) Å P m / 2 /c / P m / 2  0c ,
where 0 ° c õ  m/2  . Then,
Theorem 4.3. Let m ¢ 6 and 3 ° k õ m 0 k 02. Then,
G(c) ¥ G(c / 1).
Proof. Let m ¢ 5. For a fixed c, let k Å  m/2 / c.
From Theorem 3.2, it suffices to show that
if k is odd
Ck / Cm0k ≥ Ck/2 / Cm0k02
if k is even.
and
A(Pk )A(Pm0k ) ú A(Pk/1 )A(Pm0k01 ),
or, equivalently, that
Ck / Cm0k ¥ Ck/2 / Cm0k02
j
Theorem 4.4. Let m ¢ 6 and 3 ° k õ m 0 k 0 1.
Then,
(x 2 k 0 1)(x 2 ( m0k ) 0 1) ú (x 2 ( k/ 1 ) 0 1)(x 2 ( m0k0 1 ) 0 1).
We multiply this out and simplify algebraically to get the
inequality
4.2. RANKING CYCLE COMPONENTS
We now proceed to consider collections of cycles in the
complement graph. The next theorem is new and allows
us to extend the work done by Kel’mans [14], Kel’mans
and Chelnokov [17], and Petingi [21]. Petingi has a version of the following where k is fixed at three.
Theorem 4.2. Let m ¢ 6 and 3 ° k ° m 0 k. Then,
Ck / Cm0k ¥ Cm
Ck / Cm0k ≥ Ck/1 / Cm0k01
if k is even.
j
The proofs of these results are a straightforward application of our algebraic technique, so we omit them. Complete details can be found in [10].
4.3. Ranking Mixed Path and Cycle
Components
We first show that replacing a cycle and an isolated vertex
with a path increases the number of spanning trees. Kel’mans [14, Lemma 6.9, p. 258] also proved this using a
different proof technique.
Theorem 4.5. For k ¢ 3 (and n ¢ 5), Pk/1 ¥ Ck / P1 .
Proof. By Theorem 3.2, we need to prove that
if k is odd
(x 2 ( k/ 1 ) 0 1) 0 (x k / dk ) 2 (x 2 0 1) ú 0.
and
Ck / Cm0k ≥ Cm
We actually prove something stronger, namely, that (replacing dk by 1)
if k is even.
Proof. We apply Theorem 3.2 and note that it suffices
to compare the square roots of each term (this works
when all components are cycles). Multiplying out and
canceling terms results in the equation
dm0k x k / dk x m0k / dkdm0k 0 dm ú 0.
/ 8U11\$\$0766
06-09-97 15:09:59
(x 2 ( k/ 1 ) 0 1) 0 (x k / 1) 2 (x 2 0 1) ú 0.
This implies that
x 2 k 0 2x k/ 2 / 2x k 0 x 2 ú 0.
(1)
A simple truth table can be used to show that dkdm0k
Å 0 dm . Thus, it is obvious (since x ú 2 by Lemma 3.1,
and by definition, k ° m 0 k) that Eq. (1) has the same
sign as dk , thus proving our theorem.
j
The above theorem compares one large cycle with two
smaller ones. The next two theorems compare pairs of
cycles. The first theorem compares two pairs of cycles in
8U11
if k is odd
and
(x 2 0 1)(x 2 k 0 x 2 ( m0k0 1 ) ) ú 0.
But this is obviously true because x ú 2 (Lemma 3.1),
and by definition, k ú m 0 k 0 1.
j
Ck / Cm0k ¥ Ck/1 / Cm0k01
But this is true because k ¢ 3 and x ú 2 (Lemma 3.1).
j
We now show that C3 / Pk03 ¥ Pk , for k ¢ 5. Kel’mans stated this result without proof in [14, p. 260].
Theorem 4.6. Let k ¢ 4 (and n ¢ 5). Then,
netwas
W: Networks
766
28
GILBERT AND MYRVOLD
Lemma 4.8.
(a) C3 / P3 / P2 ¥ P4 / P4
(b) C3 / 3r P2 ¥ 3r P3
(c) C3 / 2r P2 ¥ P4 / P3 .
C3 / Pk03 ¥ Pk .
Proof. By Theorem 3.2, we need to show that
A(C3 )A(Pk03 ) 0 A(Pk ) ú 0,
Petingi’s Lemma 5.10 parts (a), (d), and (e) [21, p.
38] are equivalent to our Lemma 4.8 parts (a), (b), and
(c), respectively.
or, equivalently, that
(x3 / 1) 2 (x 2 ( k0 3 ) 0 1) 0 (x 2 k 0 1) ú 0.
Simplify algebraically to get
5. MAXIMIZING SPANNING TREES
(2x 2 k0 3 0 x 6 ) / (x 2 k0 6 0 2x 3 ) ú 0.
Each parenthesized term (and, hence, the whole expression) is clearly positive since x ú 2 (Lemma 3.1) and k
¢ 5.
j
Next, we show that a 3-cycle and a path is better than
a larger cycle and shorter path. Kel’mans states that this
can be proved [15, Note, p. 260] and Petingi also mentions it [21, Fact 3.8, p. 33] referring to Kel’mans for
the proof.
Theorem 4.7. Let k 0 c ú 0, and let c ú 0. Then,
C3 / Pk ¥ C3/c / Pk0c .
Proof. By Theorem 3.2, we need to show that
A(C3 )A(Pk ) 0 A(C3/c )A(Pk0c ) ú 0.
We actually show something stronger, namely, that (replacing dk by 1)
A(C3 )A(Pk ) 0 (x c/ 3 / 1) 2 A(Pk0c ) ú 0.
We do this by demonstrating that the maximum value of
(x c/ 3 / 1) 2 A(Pk0c ) given that c ¢ 0 is attained when c
Å 0 (corresponding to C3 and Pk ).
If we multiply out the expression (x c/ 3 / 1) 2 A(Pk0c )
and ignore the terms that are independent of c, we get
2x 2 k0c/ 3 / x 2 k0 2 c 0 x 2 c/ 6 0 2x c/ 3 .
The first two positive terms are clearly maximized when
c Å 0. Also, the last two terms make the smallest negative
contribution when c Å 0.
j
The special cases in this next lemma are needed to
characterize the graphs with the most trees. The proofs
are straightforward applications of our algebra and so we
omit them.
8U11
/ 8U11\$\$0766
j
06-09-97 15:09:59
All along, we have been considering graphs whose complements are a union of paths and cycles (including isolated vertices which are P1 ). In this section, we characterize the graphs in this family with the most trees. It is
useful to first consider how the cycles should be configured in a graph with the most trees.
Lemma 5.1. The 2-regular (n, m)-graph (n ¢ 5) whose
complement contains a maximum number of trees consists
of C3’s and at most one of a C4 or a C5 .
Proof. In the graph with the most trees, there are no
spanning tree increasing operations that can be applied.
We use this fact to isolate the structure of the graphs with
the most trees.
First, the best graph has no Ck’s for k ¢ 6 because by
Theorem 4.2 replacing Ck , k ¢ 6, by C3 and Ck03 increases
the number of trees. Consequently, all cycles in the best
graphs have length at most five.
If there is a C4 and a C5 , replacing these by C3 and C6
increases the number of trees (Theorem 4.4). Therefore,
there can be C4’s or C5’s but not both.
If there are two C4’s, replacing them by C3 and C5
increases the number of trees again by Theorem 4.4. Similarly, if there are two C5’s, replacing them by C3 and C7
increases the number of trees (Theorem 4.3).
Thus, we have shown that the best graph has all C3’s
except for possibly either one C4 or one C5 as required.
j
We are now ready to characterize the almost-regular
graphs with a maximum number of trees. The proof is
original, but the only new conclusions are the situations
with n or n 0 1 edges removed from the complete graph
not covered by [4] (described in the introduction).
Theorem 5.2. Of the family of (n, m)-graphs consisting
of a union of paths and cycles, the ones for which the
complements have a maximum number of trees are the
almost-regular graphs equal to
1. For m õ n/2, P2’s and P1’s.
netwas
W: Networks
766
MAXIMIZING SPANNING TREES IN ALMOST COMPLETE GRAPHS
2. For n/2 ° m ° n 02, C3’s, and P2’s and either P2
or P3 or two P3’s.
3. For m Å n 0 1, C3’s, and P2’s and either P2 or P3
or P4 .
4. For m Å n, at most one of C4 or C5 plus C3’s.
REFERENCES
[1]
[2]
Proof. First, the degree sequence is almost regular because of Theorem 4.5, or, equivalently, if there are isolated vertices, then there are no cycles.
Next, the paths are as even in length as possible by
Theorem 4.1. Furthermore, the paths contain at most two
degree two vertices in total since Theorem 4.6 and Lemma
4.8 combined indicate that if there are more than two
degree two vertices in paths the number of trees is increased by shortening the paths and adding a C3 .
By Lemma 5.1, the collection of cycles in the best
graph is all 3-cycles except possibly for one C4 or one
C5 . By Theorem 4.7, it is better to have a C3 with a longer
path than a C4 or a C5 with a shorter path.
j
[3]
[4]
[5]
[6]
[7]
[8]
6. FUTURE WORK
[9]
It still remains to indicate which of the graphs that we
have considered are uniformly most reliable. Some obviously are not (e.g., see [16]). The most promising avenue
of approach is a technique such as the swing surgery
[23], although may be a ‘‘reliability algebra’’ similar
to our ‘‘spanning tree algebra’’ could be developed to
distinguish between the ones with the same degree sequence.
The next open dense case for characterizing the graphs
with the most trees is when n / 1 to 3n/2 edges are
removed from the complete graph. The first step here
would be to conjecture a pattern for the best graphs. We
found it very helpful to use a program which computed
generic forms when developing the pattern for the range
that we considered and recommend this as a first step.
To date, except for the trivial cases on n 0 1 or fewer
edges, all known (n, m)-graphs with a maximum number
of trees are almost-regular. Furthermore, it seems intuitive
that graphs with a maximum number of trees have no
multiple edges [until you are forced to have them because
the number of edges exceeds n(n 0 1)/2]. Either eigenvalue techniques (see, e.g., [16]) or spanning tree increasing operations may prove useful in proving that these
things are necessary.
For the sparse cases, we observe that in the known
cases the underlying 3-regular substructure is the optimal
3-regular graph. We conjecture that this is always true
and that edges are subdivided as evenly as possible, but
not necessarily in some order such as in Figures 1 and 2.
8U11
/ 8U11\$\$0766
06-09-97 15:09:59
29
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
netwas
F. T. Boesch, On unreliability polynomials and graph
connectivity in reliable network synthesis. J. Graph Theory 10(3) (1986) 339–352.
F. T. Boesch and C. L. Suffel, A survey of the algebraic
approach to the study of spanning trees. Unpublished
report (1984).
F. T. Boesch, X. Li, and C. Suffel, On the existence
of uniformly optimally reliable networks. Networks 21
(1991) 181–194.
J. A. Bondy and U. S. R. Murty, Graph Theory with
Applications. North-Holland, New York (1980).
R. A. Brualdi and H. J. Ryser, Combinatorial Matrix
Theory. Cambridge University Press, New York (1991).
C.-S. Cheng, Optimality of certain asymmetrical experimental designs. Ann. Stat. 6 (1978) 1239–1261.
C.-S. Cheng, Maximizing the total number of spanning
trees in a graph; two related problems in graph theory
and optimum design theory. J. Combin. Theory, Ser. B
31 (1981) 240–248.
C. J. Colbourn, The Combinatorics of Network Reliability. Oxford University Press, New York (1987).
D. M. Cvetković, M. Doob, and H. Sachs, Spectra of
Graphs. Academic Press, New York (1980).
A. Gibbons, Algorithmic Graph Theory. Cambridge University Press, Cambridge (1989).
B. Gilbert, Maximizing spanning trees in almost complete graphs. Master’s Thesis, Department of Computer
Science, University of Victoria, Victoria, BC (1995).
A. K. Kel’mans, The number of trees in a graph, I.
Automation and Remote Control—Translated from: Avtomatika i Telemekhanika (Russian) 26(12) (1965)
2194–2204.
A. K. Kel’mans, The number of trees in a graph, II.
Automation and Remote Control—Translated from: Avtomatika i Telemekhanika (Russian) 27(2) (1966) 56–
65.
A. K. Kel’mans, Comparison of graphs by their number
of spanning trees. Discr. Math. 16(3) (1976) 241–261.
A. K. Kel’mans, Graphs with an extremal number of
spanning trees: A research announcement. J. Graph Theory 4 (1980) 119–122.
A. K. Kel’mans, On graphs with randomly deleted edges.
Acta Math. Acad. Sci. Hung. 37(1–3) (1981) 77–88.
A. K. Kel’mans and V. M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of
trees. J. Combin. Theory, Ser. B 16 (1974) 197–214.
G. Kirchhoff, Über die Ausflösung der Gleichungen auf
welche man bei der Untersuchungen der Linearen Verteilung Galvanisher Ströme geführt wird. Poggendorf
Ann. Phys. 72 (1847) 497–508.
J. W. Moon, Enumerating labelled trees. Graph Theory
and Theoretical Physics, (F. Harary, Ed.). Academic
Press, New York (1967) 261–272.
W: Networks
766
30
GILBERT AND MYRVOLD
[20]
W. Myrvold, K. H. Cheung, L. B. Page, and J. E. Perry,
Uniformly-most reliable networks do not always exist.
Networks 21 (1991) 417–419.
L. Petingi, On the characterization of graphs with maximum number of spanning trees. PhD Thesis, Stevens
Institute of Technology, Hoboken, NJ (1991).
L. Petingi, F. Boesch, and C. Suffel, On the characterization of graphs with maximum number of spanning trees.
Accepted to Discrete Mathematics, 1997.
A. Satyanarayana, L. Schoppmann, and C. L. Suffel, A
reliability-improving graph transformation with applications to network reliability. Networks 22 (1992) 209–
216.
D. R. Shier, Maximizing the number of spanning trees
[21]
[22]
[23]
[24]
8U11
/ 8U11\$\$0766
06-09-97 15:09:59
[25]
[26]
[27]
[28]
netwas
in a graph with n nodes and m edges. J. Res. Nat. Bur.
Stand., Sect. B 78 (1974) 193–196.
H. N. V. Temperley, On the mutual cancellation of cluster integrals in Mayer’s fugacity series. Proceed. Phys.
Soc. 83 (1964) 3–16.
S. S. Tseng and L. R. Wang, Maximizing the number of
spanning trees of networks based on cycle basis representation. Int. J. Comput. Math. 28 (1989) 47–56.
G. Wang, A proof of Boesch’s conjecture. Networks 24
(1994) 277–284.
J. F. Wang and M. H. Wu, Network reliability analysis:
On maximizing the number of spanning trees. Proceed.
Nat. Sci. Coun. Repub. China, Part A, Phys. Sci. Eng.
11(3) (1987) 193–196.
W: Networks
766
```
###### Документ
Категория
Без категории
Просмотров
2
Размер файла
94 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа