Note on extremal problems about connected subgraph sums
Stijn Cambie (Katholieke Universiteit Leuven)
Carla Groenland (TU Delft - Discrete Mathematics and Optimization)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
For a graph G with vertex assignment c:V(G)→Z+, we define ∑v∈V(H)c(v) for a connected subgraph H 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 O.-H. S. Lo in a strong form. We show that for each n-vertex graph G, there is a vertex assignment c:V(G)→{1,⋯,12n2} 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.
help_outline