Abstract
A segment of a tree T is a path whose end vertices have degree 1 or at least 3, while all internal vertices have degree 2. The lengths of all the segments of T form its segment sequence, in analogy to the degree sequence. We address a number of extremal problems for the class of all trees with a given segment sequence. In particular, we determine the extremal trees for the number of subtrees, the number of matchings and independent sets, the graph energy, and spectral moments.
Original language | English |
---|---|
Pages (from-to) | 20-34 |
Number of pages | 15 |
Journal | Discrete Applied Mathematics |
Volume | 220 |
DOIs | |
State | Published - Mar 31 2017 |
Scopus Subject Areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics
Keywords
- Estrada index
- Graph energy
- Hosoya index
- Independent sets
- Matchings
- Merrifield–Simmons index
- Segment sequence
- Subtrees
- Trees
- Walks