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

Stijn Cambie; Bradley McCoy; Stephan Wagner; Corrine Yap

doi:10.37236/12426

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

Stijn Cambie, Bradley McCoy, Stephan Wagner, Corrine Yap

Institute of Discrete Mathematics (5050)

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Article number	P1.62
Journal	Electronic Journal of Combinatorics
Volume	31
Issue number	1
DOIs	https://doi.org/10.37236/12426
Publication status	Published - 2024

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/12426Licence: CC BY-ND 4.0

Cite this

@article{d4eaccc11b874a6c86abb18157644cf1,

title = "Bounding Mean Orders of Sub-k-Trees of k-Trees",

abstract = "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.",

author = "Stijn Cambie and Bradley McCoy and Stephan Wagner and Corrine Yap",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2024",

doi = "10.37236/12426",

language = "English",

volume = "31",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

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

AU - Cambie, Stijn

AU - McCoy, Bradley

AU - Wagner, Stephan

AU - Yap, Corrine

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85188354940&partnerID=8YFLogxK

U2 - 10.37236/12426

DO - 10.37236/12426

M3 - Article

AN - SCOPUS:85188354940

SN - 1077-8926

VL - 31

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - P1.62

ER -

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

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this