Upper Bounds for Linear Graph Codes

ABSTRACT A linear graph code is a family of graphs on vertices with the property that the symmetric difference of the edge sets of any two graphs in is also the edge set of a graph in . In this article, we investigate the maximal size of a linear graph code that does not contain a copy of a fixed graph . In particular, we show that if has an even number of edges, the size of the code is , making progress on a question of Alon. Furthermore, we show that for almost all graphs with an even number of edges, there exists such that the size of a linear graph code without a copy of is at most .