Decreasing the mean subtree order by adding k edges

Creative Commons License

Cambie S., Chen G., Hao Y., Tokar N.

Journal of Graph Theory, vol.105, no.3, pp.357-366, 2024 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 105 Issue: 3
  • Publication Date: 2024
  • Doi Number: 10.1002/jgt.23043
  • Journal Name: Journal of Graph Theory
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, MathSciNet, zbMATH
  • Page Numbers: pp.357-366
  • Keywords: mean subtree order, subtree
  • Uşak University Affiliated: No

Abstract

The mean subtree order of a given graph (Formula presented.), denoted (Formula presented.), is the average number of vertices in a subtree of (Formula presented.). Let (Formula presented.) be a connected graph. Chin et al. conjectured that if (Formula presented.) is a proper spanning supergraph of (Formula presented.), then (Formula presented.). Cameron and Mol disproved this conjecture by showing that there are infinitely many pairs of graphs (Formula presented.) and (Formula presented.) with (Formula presented.), (Formula presented.) and (Formula presented.) such that (Formula presented.). They also conjectured that for every positive integer (Formula presented.), there exists a pair of graphs (Formula presented.) and (Formula presented.) with (Formula presented.), (Formula presented.), and (Formula presented.) such that (Formula presented.). Furthermore, they proposed that (Formula presented.) provided (Formula presented.). In this note, we confirm these two conjectures.