Extremal results on average subtree density of series-reduced trees

DOI10.1016/J.JCTB.2014.02.003zbMATH Open1298.05066arXiv1312.7233OpenAlexW2949912983MaRDI QIDQ403359FDOQ403359

Authors: John Haslegrave 

Publication date: 29 August 2014

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

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.

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

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

zbMATH Keywords

subtreeaverage orderextremal sequenceseries-reduced tree

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the average number of nodes in a subtree of a tree
• Title not available (Why is that?)
• The number of homeomorphically irreducible trees, and other species
• The average order of a subtree of a tree

Cited In (30)

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