Extremal problems for trees with given segment sequence

详细信息    查看全文

• 作者：Eric Ould Dadah Andriantiana^a ; ^{E.Andriantiana@ru.ac.za} ; Stephan Wagner^b ; ^{swagner@sun.ac.za} ; Hua Wang^c ; ^{hwang@georgiasouthern.edu}
• 关键词：Trees ; Segment sequence ; Subtrees ; Independent sets ; Matchings ; Walks ; Merrifield&ndash ; Simmons index ; Hosoya index ; Graph energy ; Estrada index
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：31 March 2017
• 年：2017
• 卷：220
• 期：Complete
• 页码：20-34
• 全文大小：492 K
• 卷排序：220

文摘

A segment of a tree TT 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 TT 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.