Structured Codes of Graphs
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.
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}
}
EUVIMED