Counting trees in a graph is #P-complete

Multicolored trees in complete graphs

✍ S. Akbari; A. Alipour 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB

## Abstract A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph __K__~2__n__~(__n__ > 2) with 2__n__ − 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize thi

Multicolored Trees in Complete Graphs

✍ Richard A. Brualdi; Susan Hollingsworth 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 180 KB

We prove the existence of two edge-disjoint multicolored spanning trees in any edge-coloring of a complete graph by perfect matchings; we conjecture that a full partition into multicolored spanning trees is always possible.

Codifying trees and multitrees of a comp

Codifying trees and multitrees of a complete graph

✍ Wai-Kai Chen 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 739 KB

## Simple codes for trees and multitrees of a complete graph are presented. They can be used rather eficiently for the generation of all possible trees and multitrees of a complete or nearly complete graph. With minor nwdi$cations, the code can also be used as a generating function for labeled tre

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 👁 3 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

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

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 spa

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

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 spa