## Abstract

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 [Formula presented] 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.

Original language | English (US) |
---|---|

Article number | 103880 |

Journal | European Journal of Combinatorics |

Volume | 116 |

DOIs | |

State | Published - Feb 2024 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics