The packing number of the double vertex graph of the path graph
| Autor: | Soto, José Manuel Gómez, Leaños, Jesús, Ríos-Castro, Luis Manuel, Rivera, Luis Manuel |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | Discrete Appl. Math, 247 (2018) 327-340 |
| Druh dokumentu: | Working Paper |
| Popis: | 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. 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 |
| Databáze: | arXiv |
| Externí odkaz: |
|