Premium
On the mean subtree order of graphs under edge addition
Author(s) -
Cameron Ben,
Mol Lucas
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22621
Subject(s) - combinatorics , conjecture , mathematics , counterexample , order (exchange) , graph , enhanced data rates for gsm evolution , discrete mathematics , computer science , telecommunications , finance , economics
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.