𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximizing the number of independent subsets over trees with bounded degree

✍ Scribed by Clemens Heuberger; Stephan G Wagner

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
208 KB
Volume
58
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The number of independent vertex subsets is a graph parameter that is, apart from its purely mathematical importance, of interest in mathematical chemistry. In particular, the problem of maximizing or minimizing the number of independent vertex subsets within a given class of graphs has already been investigated by many authors. In view of the applications of this graph parameter, trees of restricted degree are of particular interest. In the current article, we give a characterization of the trees with given maximum degree which maximize the number of independent subsets, and show that these trees also minimize the number of independent edge subsets. The structure of these trees is quite interesting and unexpected: it can be described by means of a novel digital systemβ€”in the case of maximum degree 3, we obtain a binary system using the digits 1 and 4. The proof mainly depends on an exchange lemma for branches of a tree. Β© 2008 Wiley Periodicals, Inc. J Graph Theory 58: 49–68, 2008

πŸ“œ SIMILAR VOLUMES

The 2-intersection number of paths and b
The 2-intersection number of paths and bounded-degree trees
✍ Michael S. Jacobson; AndrΓ© E. KΓ©zdy; Douglas B. West πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 416 KB πŸ‘ 1 views

## Abstract We represent a graph by assigning each vertex a finite set such that vertices are adjacent if and only if the corresponding sets have at least two common elements. The __2‐intersection number__ ΞΈ~2~(__G__) of a graph __G__ is the minimum size of the union of sets in such a representatio

On the Density of Subgraphs in a Graph w
On the Density of Subgraphs in a Graph with Bounded Independence Number
✍ Pavel Valtr πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(

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