✦ LIBER ✦

A spanning tree of the 2m-dimensional hypercube with maximum number of degree-preserving vertices

✍ Scribed by Sul-young Choi; Puhua Guan

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 190 KB
Volume: 117
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90343-r

No coin nor oath required. For personal study only.

✦ Synopsis

For an n-dimensional hypercube Q., the maximum number of degree-preserving vertices in a spanning tree is 2"jn if n = 2" for an integer M. (If n # 2", then the maximum number of degree-preserving vertices in a spanning tree is less than 2"/n.) We also construct a spanning tree of Qzm with maximum number of degree-preserving vertices.

📜 SIMILAR VOLUMES

On numbers of vertices of maximum degree

On numbers of vertices of maximum degree in the spanning trees of a graph

✍ Jerzy Topp; Preben D. Vestergaard 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 611 KB

For a connected graph G, let ~-(G) be the set of all spanning trees of G and let nd(G) be the number of vertices of maximum degree in G. In this paper we show that if G is a cactus or a connected graph with p vertices and p+ 1 edges, then the set {na(T) : T C ~-(G)) has at most one gap, that is, it

A lower bound on the number of spanning

A lower bound on the number of spanning trees with k end-vertices

✍ Katherine Heinrich; Guizhen Liu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB 👁 1 views

If a graph G with cycle rank p contains both spanning trees with rn and with n end-vertices, rn < n, then G has at least 2p spanning trees with k end-vertices for each integer k, rn < k < n. Moreover, the lower bound of 2p is best possible. [ l ] and Schuster [4] independently proved that such span