Note on extremal problems about connected subgraph sums
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911054289698816 |
|---|---|
| author | Cambie, Stijn Groenland, Carla |
| author_facet | Cambie, Stijn Groenland, Carla |
| contents | 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'\not\cong G$ and vertex assignment $c'$ for $G'$, the corresponding collections of connected subgraph sums are different (i.e., $S(G,c)\neq S(G',c')$). We also provide some remarks on vertex assignments of a graph $G$ for which all connected subgraph sums are different. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10114 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Note on extremal problems about connected subgraph sums Cambie, Stijn Groenland, Carla Combinatorics 05C35, 05C69, 05C60 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'\not\cong G$ and vertex assignment $c'$ for $G'$, the corresponding collections of connected subgraph sums are different (i.e., $S(G,c)\neq S(G',c')$). We also provide some remarks on vertex assignments of a graph $G$ for which all connected subgraph sums are different. |
| title | Note on extremal problems about connected subgraph sums |
| topic | Combinatorics 05C35, 05C69, 05C60 |
| url | https://arxiv.org/abs/2507.10114 |