Note on extremal problems about connected subgraph sums

Abstract

For a graph $G$ with vertex assignment $c:V(G)\to {\mathbb{Z}}^{+}$, we define ${\sum }_{v\in V(H)}c(v)$ for $H$ a connected subgraph of $G$ as a connected subgraph sum of $G$. We study the set $S(G,c)$ of connected subgraph sums and, in particular, resolve a problem posed by Solomon Lo in a strong form. We show that for each $n$-vertex graph, there is a vertex assignment $c:V(G)\to \{1,\dots ,12n^2\}$ such that for every $n$-vertex graph $G^{\prime }\ncong G$ and vertex assignment $c^{\prime }$ for $G^{\prime }$, the corresponding collections of connected subgraph sums are different (i.e., $S(G,c)\ne S(G^{\prime },c^{\prime })$). We also provide some remarks on vertex assignments of a graph $G$ for which all connected subgraph sums are different.

5 Pages, 2 Figures