Decreasing the mean subtree order by adding k edges

Creative Commons License

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

Journal of Graph Theory, cilt.105, sa.3, ss.357-366, 2024 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 105 Sayı: 3
  • Basım Tarihi: 2024
  • Doi Numarası: 10.1002/jgt.23043
  • Dergi Adı: Journal of Graph Theory
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, MathSciNet, zbMATH
  • Sayfa Sayıları: ss.357-366
  • Anahtar Kelimeler: mean subtree order, subtree
  • Uşak Üniversitesi Adresli: Hayır

Özet

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.