✦ LIBER ✦

Maximizing spanning trees in almost complete graphs

✍ Scribed by Gilbert, Bryan; Myrvold, Wendy

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 94 KB
Volume: 30
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199708)30:1<23::aid-net3>3.0.co;2-n

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Maximizing spanning trees in almost comp

Maximizing spanning trees in almost complete graphs

✍ Gilbert, Bryan; Myrvold, Wendy 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB 👁 2 views

Special monochromatic trees in two-color

Special monochromatic trees in two-colored complete graphs

✍ Chen, Guantao; Schelp, Richard H.; ?olt�s, ?ubom�r 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB 👁 2 views

For a positive integer k, a set of k + 1 vertices in a graph is a k-cluster if the difference between degrees of any two of its vertices is at most k -1. Given any tree T with at least k 3 edges, we show that for each graph G of sufficiently large order, either G or its complement contains a copy of

On the asymptotic behavior of the maximu

On the asymptotic behavior of the maximum number of spanning trees in circulant graphs

✍ Lonc, Zbigniew; Parol, Krzysztof; Wojciechowski, Jacek M. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 2 views

The following asymptotic estimation of the maximum number of spanning trees f k (n) in 2kregular circulant graphs ( k ú 1) on n vertices is the main result of this paper: )) , where

Remarks on the placeability of isomorphi

Remarks on the placeability of isomorphic trees in a complete graph

✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 2 views

Let Tp be any tree of order p and A ( T p ) stand for the maximum degree of the vertices of Tp. We prove the following theorem. "If A(Tp) 5 pi, where p > 2i, then Tp is i-placeable in Kp" is true if and only if i = 1, 2, and 3. 0 1996 John Wiley & Sons, Inc. Suppose G is a graph and V ( G ) , E ( G

Calculating the number of spanning trees

Calculating the number of spanning trees in a labeled planar molecular graph whose inner dual is a tree

✍ P. E. John; R. B. Mallion 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 496 KB 👁 2 views

The quantum mechanical relevance of the concept of a spanning tree extant within a given molecular graph-specifically, one that may be considered to represent the carbon-atom connectivity of a particular (planar) conjugated system-was first explicitly pointed out by Professor Roy McWeeny in his now-