Connectivity graph-codes

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
JournalRandom Structures and Algorithms
DOIs
StateAccepted/In press - 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

Fingerprint

Dive into the research topics of 'Connectivity graph-codes'. Together they form a unique fingerprint.

Cite this