On the mean subtree order of graphs under edge addition

Abstract

Abstract For a graph , the mean subtree order of is the average order of a subtree of . In this note, we provide counterexamples to a recent conjecture of Chin, Gordon, MacPhee, and Vincent, that for every connected graph and every pair of distinct vertices and of , the addition of the edge between and 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 can decrease the mean subtree order by as much as asymptotically. We propose the weaker conjecture that for every connected graph which is not complete, there exists a pair of nonadjacent vertices and , such that the addition of the edge between and increases the mean subtree order. We prove this conjecture in the special case that is a tree.

Locations

• Journal of Graph Theory - View
• arXiv (Cornell University) - View - PDF