Abstract
The symmetric difference of two graphs (Formula presented.) on the same set of vertices (Formula presented.) is the graph on (Formula presented.) whose set of edges are all edges that belong to exactly one of the two graphs (Formula presented.). For a fixed graph (Formula presented.) call a collection (Formula presented.) of spanning subgraphs of (Formula presented.) a connectivity code for (Formula presented.) if the symmetric difference of any two distinct subgraphs in (Formula presented.) is a connected spanning subgraph of (Formula presented.). It is easy to see that the maximum possible cardinality of such a collection is at most (Formula presented.), where (Formula presented.) is the edge-connectivity of (Formula presented.) and (Formula presented.) is its minimum degree. We show that equality holds for any (Formula presented.) -regular (mild) expander, and observe that equality does not hold in several natural examples including any large cubic graph, the square of a long cycle and products of a small clique with a long cycle.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 451-459 |
| Number of pages | 9 |
| Journal | Random Structures and Algorithms |
| Volume | 65 |
| Issue number | 3 |
| DOIs | |
| State | Published - Oct 2024 |
All Science Journal Classification (ASJC) codes
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
Keywords
- connectivity
- error correcting codes
- expanders
- graph codes