2019/11/13 by Ben Cameron, Lucas Mol, Cameron, Ben +1 · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1911.05794
For a graph G, the mean subtree order of G is the average order of a subtree of G. In this note, we provide counterexamples to a recent conjecture of Chin, Gordon, MacPhee, and Vincent, that for every connected graph G and every pair of distinct vertices u and v of G, the addition of the edge between u and v increases the mean subtree order. In fact, we show that the addition of a single edge between a pair of nonadjacent vertices in a graph of order n can decrease the mean subtree order by as much as n/3 asymptotically. We propose the weaker conjecture that for every connected graph G which is not complete, there exists a pair of nonadjacent vertices u and v, such that the addition of the edge between u and v increases the mean subtree order. We prove this conjecture in the special case that G is a tree.