EUVIMEDEUVIMED entdecken
Crossref

Structured Codes of Graphs

Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojević, Gábor Simonyi

SIAM Journal on Discrete Mathematics · 31.03.2023 · 37 (1) · 379-403

DOI: 10.1137/22m1487989 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 03.03.2023. Verfasst von Noga Alon und 4 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 43 Literaturangaben. Gefördert von: National Science Foundation, Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, United States - Israel Binational Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We investigate the maximum size of graph families on a common vertex set of cardinality [Formula: see text] such that the symmetric difference of the edge sets of any two members of the family satisfies some prescribed condition. We solve the problem completely for infinitely many values of [Formula: see text] when the prescribed condition is connectivity or 2-connectivity, Hamiltonicity, or the containment of a spanning star. We also investigate local conditions that can be certified by looking at only a subset of the vertex set. In these cases a capacity-type asymptotic invariant is defined and when the condition is to contain a certain subgraph this invariant is shown to be a simple function of the chromatic number of this required subgraph. This is proven using classical results from extremal graph theory. Several variants are considered and the paper ends with a collection of open problems.

Förderung

  • National Science Foundation
  • Nemzeti Kutatási Fejlesztési és Innovációs Hivatal
  • United States - Israel Binational Science Foundation

Zitieren

APA

Alon, N., Gujgiczer, A., Körner, J., Milojević, A., & Simonyi, G. (2023). Structured Codes of Graphs. SIAM Journal on Discrete Mathematics, 37(1), 379-403. https://doi.org/10.1137/22m1487989

Vancouver

Alon N, Gujgiczer A, Körner J, Milojević A, Simonyi G. Structured Codes of Graphs. SIAM Journal on Discrete Mathematics. 2023;37(1):379-403. doi:10.1137/22m1487989

BibTeX
@article{Alon2023,
  author = {Alon, Noga and Gujgiczer, Anna and Körner, János and Milojević, Aleksa and Simonyi, Gábor},
  title = {Structured Codes of Graphs},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2023},
  volume = {37},
  number = {1},
  pages = {379--403},
  doi = {10.1137/22m1487989}
}
Kostenlos starten →