Back to Search
Start Over
The packing number of the double vertex graph of the path graph
- Publication Year :
- 2017
- Publisher :
- arXiv, 2017.
-
Abstract
- Neil Sloane showed that the problem of determine the maximum size of a binary code of constant weight 2 that can correct a single adjacent transposition is equivalent to finding the packing number of a certain graph. In this paper we solve this open problem by finding the packing number of the double vertex graph (2-token graph) of a path graph. This double vertex graph is isomorphic to the Sloane's graph. Our solution implies a conjecture of Rob Pratt about the ordinary generating function of sequence A085680.<br />Comment: 21 pages, 7 figures. V2: 22 pages, more figures added. V3. minor corrections based on referee's comments. One figure corrected. The title "On an error correcting code problem" has been changed
- Subjects :
- Conjecture
Applied Mathematics
Open problem
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Graph
Combinatorics
94B05, 94B65, 05C70, 05C76
010201 computation theory & mathematics
0202 electrical engineering, electronic engineering, information engineering
FOS: Mathematics
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
020201 artificial intelligence & image processing
Path graph
Maximum size
Binary code
Combinatorics (math.CO)
Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....9690e06570775e56ed3ee2040a647c50
- Full Text :
- https://doi.org/10.48550/arxiv.1711.03682