TY - JOUR
T1 - Graph-codes
AU - Alon, Noga
N1 - Publisher Copyright:
© 2023
PY - 2024/2
Y1 - 2024/2
N2 - The symmetric difference of two graphs G1,G2 on the same set of vertices [n]={1,2,…,n} is the graph on [n] whose set of edges are all edges that belong to exactly one of the two graphs G1,G2. Let H be a fixed graph with an even (positive) number of edges, and let DH(n) denote the maximum possible cardinality of a family of graphs on [n] containing no two members whose symmetric difference is a copy of H. Is it true that [Formula presented] for any such H? We discuss this problem, compute the value of DH(n) up to a constant factor for stars and matchings, and discuss several variants of the problem including ones that have been considered in earlier work.
AB - The symmetric difference of two graphs G1,G2 on the same set of vertices [n]={1,2,…,n} is the graph on [n] whose set of edges are all edges that belong to exactly one of the two graphs G1,G2. Let H be a fixed graph with an even (positive) number of edges, and let DH(n) denote the maximum possible cardinality of a family of graphs on [n] containing no two members whose symmetric difference is a copy of H. Is it true that [Formula presented] for any such H? We discuss this problem, compute the value of DH(n) up to a constant factor for stars and matchings, and discuss several variants of the problem including ones that have been considered in earlier work.
UR - http://www.scopus.com/inward/record.url?scp=85176957923&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85176957923&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2023.103880
DO - 10.1016/j.ejc.2023.103880
M3 - Article
AN - SCOPUS:85176957923
SN - 0195-6698
VL - 116
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103880
ER -