Extremal results on average subtree density of series-reduced trees

DOI10.1016/J.JCTB.2014.02.003MaRDI QIDQ403359zbMATH OpenOpenAlexFDO

Authors John Haslegrave

Publication date 29 August 2014

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

subtreeaverage orderextremal sequenceseries-reduced tree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42)

Abstract: Vince and Wang showed that the average subtree density of a series-reduced tree is between 1/2 and 3/4, answering a conjecture of Jamison. They ask under what conditions a sequence of such trees may have average subtree density tending to either bound; we answer these questions by giving simple necessary and sufficient conditions in each case.

Recommendations

• The average order of a subtree of a tree
• On the mean subtree order of trees under edge contraction
• scientific article; zbMATH DE number 3849285
• On the maximum mean subtree order of trees
• A lower bound on the average size of a connected vertex set of a graph

Cites work

• scientific article; zbMATH DE number 3849252 (Why is no real title available?)
• scientific article; zbMATH DE number 193053 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• On the average number of nodes in a subtree of a tree
• The average order of a subtree of a tree
• The number of homeomorphically irreducible trees, and other species

Cited in

(30)

• The distance spectral radius of trees
• On the maximum mean subtree order of trees
• Random subtrees and unimodal sequences in graphs
• Minimum status of series-reduced trees with given parameters
• On the eccentric subtree number in trees
• On the mean subtree order of trees under edge contraction
• The average order of dominating sets of a graph
• Which numbers are status differences?
• The average size of a connected vertex set of a graph—Explicit formulas and open problems
• On the roots of the subtree polynomial
• On the maximum local mean order of sub-\(k\)-trees of a \(k\)-tree
• Decreasing the mean subtree order by adding k edges
• Multi-distance granularity structural \(\alpha \)-subtree index of generalized Bethe trees
• The path minimises the average size of a connected induced subgraph
• The number and average size of connected sets in graphs with degree constraints
• Solution to a conjecture on the mean subtree order of graphs under edge addition
• On the difference of mean subtree orders under edge contraction
• On spiro and polyphenyl hexagonal chains with respect to the number of BC-subtrees
• The expected subtree number index in random polyphenylene and spiro chains
• On the probability that a random subtree is spanning
• A lower bound on the average size of a connected vertex set of a graph
• The average size of matchings in graphs
• On the mean subtree order of graphs under edge addition
• On enumerating algorithms of novel multiple leaf-distance granular regular \(\alpha\)-subtrees of trees
• The average size of a connected vertex set of a \(k\)-connected graph
• Trees with large numbers of subtrees
• Subtrees of spiro and polyphenyl hexagonal chains
• Enumeration of subtrees and BC-subtrees with maximum degree no more than \(k\) in trees
• On the local and global mean orders of sub-\(k\)-trees of \(k\)-trees
• The average size of independent sets of graphs

This page was built for publication: Extremal results on average subtree density of series-reduced trees

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