.png){kind=icon}
返回
Note on extremal problems about connected subgraph sums
.png){kind=icon}
PRE
AI
DOI：10.1007/s00373-026-03026-8.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
对于具有顶点赋值 c:V(G)→Z+ 的图 G，我们将对于 G 的一个连通子图 H 定义的 ∑v∈V(H)c(v) 称为 G 的一个连通子图和。我们研究连通子图和的集合 S(G, c)，特别是在强形式下解决由 O.-H. S. Lo 提出的问题。我们证明，对于每个 n 个顶点的图 G，存在一个顶点赋值 c:V(G)→{1,⋯,12n2}，使得对于每个与 G 不全等的 n 个顶点的图 G' 和其顶点赋值 c'，对应的连通子图和的集合是不同的（即 S(G, c) ≠ S(G', c'））。我们还对使得所有连通子图和都不同的图的顶点赋值提供了一些说明。
Keyword:
Connected subgraph sums
Sidon set
Golomb ruler
Graph reconstruction
Graph labelling
