The Graph-codes

The symmetric difference of two graphs G(1), G(2) 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 G(1), G(2). Let H be a fixed graph with an even (positive) number of edges, and let D-H(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 D-H(n) = o(2((n)(2))) for any such H? We discuss this problem, compute the value of D-H(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.(c) 2023 Published by Elsevier Ltd.

Automated summary

This study discusses the problem of fixed graph H with an even number of edges and explores the properties of D-H(n) and possible upper bounds.