2025/07/14 by Stijn Cambie, Cambie, Stijn, Carla Groenland +1
Mathematics · #05C35 #05C60 #05C69 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2507.10114
openalex publication_date 2025/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G with vertex assignment c:V(G)→ ℤ+, 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,…,12n2\ such that for every n-vertex graph G'\not≅ 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.