Extremal problems for trees with given segment sequence

Eric Ould Dadah Andriantiana, Stephan Wagner, Hua Wang

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

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 languageEnglish
Pages (from-to)20-34
Number of pages15
JournalDiscrete Applied Mathematics
Volume220
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Extremal problems for trees with given segment sequence'. Together they form a unique fingerprint.

Cite this