Extremal trees with fixed degree sequence

DOI10.37236/9770MaRDI QIDQ2223451zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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

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)

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.

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

Cites work

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

Cited in

(17)

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

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)