Extremal trees with fixed degree sequence

DOI10.37236/9770zbMATH Open1461.05030arXiv2008.00722OpenAlexW3119233936MaRDI QIDQ2223451FDOQ2223451

Authors: Eric Ould Dadah Andriantiana, Valisoa Razanajatovo Misanantenaina, Stephan Wagner 

Publication date: 29 January 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: The greedy tree $mathcalG(D)$ and the $mathcalM$-tree $mathcalM(D)$ are known to be extremal among trees with degree sequence $D$ with respect to various graph invariants. This paper provides a general theorem that covers a large family of invariants for which $mathcalG(D)$ or $mathcalM(D)$ is extremal. Many known results, for example on the Wiener index, the number of subtrees, the number of independent subsets and the number of matchings follow as corollaries, as do some new results on invariants such as the number of rooted spanning forests, the incidence energy and the solvability. We also extend our results on trees with fixed degree sequence $D$ to the set of trees whose degree sequence is majorised by a given sequence $D$, which also has a number of applications.

Full work available at URL: https://arxiv.org/abs/2008.00722

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A note on extremal trees with degree conditions
• Greedy trees, caterpillars, and Wiener-type graph invariants
• Extremal trees with respect to functions on adjacent vertex degrees
• Greedy trees, subtrees and antichains
• Functions on adjacent vertex degrees of trees with given degree sequence

zbMATH Keywords

treesdegree sequencegreedy treeM-tree

Mathematics Subject Classification ID

Trees (05C05) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Distance in graphs (05C12)

Cites Work

• Signless Laplacians of finite graphs
• Title not available (Why is that?)
• Chemical trees minimizing energy and Hosoya index
• Wiener index versus maximum degree in trees
• On subtrees of trees
• Laplacian coefficient, matching polynomial and incidence energy of trees with described maximum degree
• Largest Number of Subtrees of Trees with a Given Maximum Degree
• Title not available (Why is that?)
• Incidence energy of a graph
• On incidence energy of graphs
• Maximizing the number of independent subsets over trees with bounded degree
• A Laplacian-energy-like invariant of a graph
• Wiener index of trees: Theory and applications
• The Laplacian spectral radii of trees with degree sequences
• The Steiner Wiener index of a graph
• Steiner distance in graphs
• Greedy trees, caterpillars, and Wiener-type graph invariants
• Variations of distance-based invariants of trees
• Title not available (Why is that?)
• Greedy trees, subtrees and antichains
• The number of subtrees of trees with given degree sequence
• The extremal values of the Wiener index of a tree with given degree sequence
• Energy, Hosoya index and Merrifield-Simmons index of trees with prescribed degree sequence
• Title not available (Why is that?)
• The sum of the distances between the leaves of a tree and the `semi-regular' property
• Terminal Wiener index
• Graphs with given degree sequence and maximal spectral radius
• Functions on adjacent vertex degrees of trees with given degree sequence
• On the Wiener index of trees with given number of branching vertices
• On the minimal energy of trees with a given number of pendent vertices
• Laplacian coefficients of trees with given number of leaves or vertices of degree two
• Minimum energy on trees with \(k\) pendent vertices
• Spectral moments of trees with given degree sequence
• The Merrifield - Simmons indices and Hosoya indices of trees with \(k\) pendant vertices
• Combinatorial properties of a general domination problem with parity constraints
• On trees with given number of pendant edges and their Wiener indices
• Extremal trees with respect to the Steiner Wiener index
• On majorization of closed walk vectors of trees with given degree sequences

Cited In (17)

• Functions on adjacent vertex degrees of trees with given degree sequence
• Extremal trees with respect to functions on adjacent vertex degrees
• Extremal trees with respect to dominance order.
• Trees with the same degree sequence and path numbers
• Maximum trees of finite sequences
• A note on extremal trees with degree conditions
• Greedy trees, subtrees and antichains
• The minimal number of subtrees with a given degree sequence
• Steiner Wiener index and line graphs of trees
• The signless \(p\)-Laplacian spectral radius of graphs with given degree sequences
• Extremal graph theory for degree sequences
• The number of subtrees of trees with given degree sequence
• Extremal properties of graphs and eigencentrality in trees with a given degree sequence
• An alternative proof of the Sombor index minimizing property of greedy trees
• Note on Sombor index of connected graphs with given degree sequence
• Extremal problems for trees with given segment sequence
• Greedy trees, caterpillars, and Wiener-type graph invariants

This page was built for publication: Extremal trees with fixed degree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223451)