Codes with structured Hamming distance in graph families
share
We investigate the maximum size of graph families on a common vertex set of cardinality n such that the symmetric difference of the edge sets of any two members of the family satisfies some prescribed condition. We solve the problem completely for infinitely many values of n when the prescribed condition is connectivity or 2-connectivity, Hamiltonicity or the containment of a spanning star. We give lower and upper bounds when it is the containment of some fixed finite graph concentrating mostly on the case when this graph is the 3-cycle or just any odd cycle. The paper ends with a collection of open problems followed by an important update in this new version of the manuscript..
READ FULL TEXT