Bounding Mean Orders of Sub-$k$-Trees of $k$-Trees

For a $k$-tree $T$, we prove that the maximum local mean order is attained in a $k$-clique of degree $1$ and that it is not more than twice the global mean order. We also bound the global mean order if $T$ has no $k$-cliques of degree $2$ and prove that for large order, the $k$-star attains the mini...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2024-03, Vol.31 (1)
Main Authors: Cambie, Stijn, McCoy, Bradley, Wagner, Stephan, Yap, Corrine
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a $k$-tree $T$, we prove that the maximum local mean order is attained in a $k$-clique of degree $1$ and that it is not more than twice the global mean order. We also bound the global mean order if $T$ has no $k$-cliques of degree $2$ and prove that for large order, the $k$-star attains the minimum global mean order. These results solve the remaining problems of Stephens and Oellermann [J. Graph Theory 88 (2018), 61-79] concerning the mean order of sub-$k$-trees of $k$-trees.
ISSN:1077-8926
1097-1440
1077-8926
DOI:10.37236/12426