EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Note on extremal problems about connected subgraph sums

Stijn Cambie, Carla Groenland iD

Graphs and Combinatorics · 2026-04 · 42 (2)

DOI: 10.1007/s00373-026-03026-8 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Graphs and Combinatorics, online erschienen am 06.03.2026. Verfasst von Stijn Cambie und 1 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, KU Leuven Campus Kulak-Kortrijk, 8500 Kortrijk, Belgium. Die Arbeit nennt 6 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Nederlandse Organisatie voor Wetenschappelijk Onderzoek, Fonds Wetenschappelijk Onderzoek.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

For a graph G with vertex assignment $$c:V(G)\rightarrow \mathbb {Z}^+$$ c : V ( G ) → Z + , we define $$\sum _{v\in V(H)}c(v)$$ ∑ 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)\rightarrow \{1,\dots ,12n^2\}$$ c : V ( G ) → { 1 , ⋯ , 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 ) ≠ S ( G ′ , c ′ ) ). We also provide some remarks on vertex assignments of a graph G for which all connected subgraph sums are different.

Schlagwörter

Stichwörter der Autor:innen

Connected subgraph sumsGolomb rulerGraph labellingGraph reconstructionSidon set

Autor:innen und Institutionen

  • Department of Computer Science, KU Leuven Campus Kulak-Kortrijk, 8500 Kortrijk, Belgium.
  • Delft Institute of Applied Mathematics, TU Delft, Delft, Netherlands.

ORCID-Profile: Carla Groenland

Förderung

  • Nederlandse Organisatie voor Wetenschappelijk Onderzoek
  • Fonds Wetenschappelijk Onderzoek

Zitieren

APA

Cambie, S., & Groenland, C. (2026). Note on extremal problems about connected subgraph sums. Graphs and Combinatorics, 42(2). https://doi.org/10.1007/s00373-026-03026-8

Vancouver

Cambie S, Groenland C. Note on extremal problems about connected subgraph sums. Graphs and Combinatorics. 2026;42(2). doi:10.1007/s00373-026-03026-8

BibTeX
@article{Cambie2026,
  author = {Cambie, Stijn and Groenland, Carla},
  title = {Note on extremal problems about connected subgraph sums},
  journal = {Graphs and Combinatorics},
  year = {2026},
  volume = {42},
  number = {2},
  doi = {10.1007/s00373-026-03026-8}
}
Kostenlos starten →