This analysis resolves extremal problems regarding connected subgraphs in graphs, suggesting unique sums for vertex assignments.
For a graph G with vertex assignment c:V(G)→ Z⁺, we define ∑v∈ 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)→ \1,,12n²\ such that for every n-vertex graph G' G and vertex assignment $c'$ for $G'$, the corresponding collections of connected subgraph sums are different (i.e., S(G,c)≠ S(G',c')). We also provide some remarks on vertex assignments of a graph G for which all connected subgraph sums are different.
No takes yet. Share an insight, caveat, or question.
Cambie et al. (2025) studied this question.