For a graph G with vertex assignment <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$c:V(G)\rightarrow \mathbb {Z}^+$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo>:</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">→</mo> <msup> <mrow> <mi mathvariant="double-struck">Z</mi> </mrow> <mo>+</mo> </msup> </mrow> </math></EquationSource> </InlineEquation>, we define <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\sum _{v\in V(H)}c(v)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mo>∑</mo> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </msub> <mi>c</mi> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$c:V(G)\rightarrow \{1,\dots ,12n^2\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo>:</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">→</mo> <mrow> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mn>12</mn> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> such that for every n-vertex graph <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$G'\not \cong G$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>G</mi> <mo>′</mo> </msup> <mo>≇</mo> <mi>G</mi> </mrow> </math></EquationSource> </InlineEquation> and vertex assignment <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$c'$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>c</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$G'$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>G</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation>, the corresponding collections of connected subgraph sums are different (i.e., <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$S(G,c)\ne S(G',c')$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>c</mi> <mo stretchy="false">)</mo> </mrow> <mo>≠</mo> <mi>S</mi> <mrow> <mo stretchy="false">(</mo> <msup> <mi>G</mi> <mo>′</mo> </msup> <mo>,</mo> <msup> <mi>c</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>). We also provide some remarks on vertex assignments of a graph G for which all connected subgraph sums are different.

Note on extremal problems about connected subgraph sums

期刊论文
出版模式：

开放获取
发表日期：

2026年3月6日

查看全文

Stijn Cambie,
Carla Groenland

摘要

For a graph G with vertex assignment $c:V(G)\rightarrow \mathbb {Z}^+$ $c : V (G) \to Z^{+}$ , we define $\sum _{v\in V(H)}c(v)$ $\sum_{v \in 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)\rightarrow \{1,\dots ,12n^2\}$ $c : V (G) \to {1, \dots, 12 n^{2}}$ such that for every n-vertex graph $G'\not \cong G$ $G^{'} ≇ G$ and vertex assignment $c'$ $c^{'}$ for $G'$ $G^{'}$ , the corresponding collections of connected subgraph sums are different (i.e., $S(G,c)\ne S(G',c')$ $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.