Paired many-to-many 2-disjoint path cover of Johnson graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915402561355776 |
|---|---|
| author | Liu, Jinhao Lü, Huazhong |
| author_facet | Liu, Jinhao Lü, Huazhong |
| contents | Given two 2 disjoint vertex-sets $S=\{u,x\}$ and $T=\{v,y\}$, a paired many-to-many 2-disjoint path cover joining S and T, is a set of two vertex-disjoint paths with endpoints $u,v$ and $x,y$, respectively, that cover every vertex of the graph. If the graph has a many-to-many 2-disjoint path cover for any two disjoint vertex-sets $S$ and $T$, then it is called paired 2-coverable. It is known that if a graph is paired 2-coverable, then it must be Hamilton-connected, but the reverse is not true. It has been proved that Johnson graphs $J(n,k)$, $0\le k\le n$, are Hamilton-connected by Brian Alspach in [Ars Math. Contemp. 6 (2013) 21--23]. In this paper, we prove that Johnson graphs are paired 2-coverable. Moreover, we obtain that another family of graphs $QJ(n,k)$ constructed from Johnson graphs by Alspach are also paired 2-coverable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_15463 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Paired many-to-many 2-disjoint path cover of Johnson graphs Liu, Jinhao Lü, Huazhong Combinatorics Discrete Mathematics 05C38, 68R10 Given two 2 disjoint vertex-sets $S=\{u,x\}$ and $T=\{v,y\}$, a paired many-to-many 2-disjoint path cover joining S and T, is a set of two vertex-disjoint paths with endpoints $u,v$ and $x,y$, respectively, that cover every vertex of the graph. If the graph has a many-to-many 2-disjoint path cover for any two disjoint vertex-sets $S$ and $T$, then it is called paired 2-coverable. It is known that if a graph is paired 2-coverable, then it must be Hamilton-connected, but the reverse is not true. It has been proved that Johnson graphs $J(n,k)$, $0\le k\le n$, are Hamilton-connected by Brian Alspach in [Ars Math. Contemp. 6 (2013) 21--23]. In this paper, we prove that Johnson graphs are paired 2-coverable. Moreover, we obtain that another family of graphs $QJ(n,k)$ constructed from Johnson graphs by Alspach are also paired 2-coverable. |
| title | Paired many-to-many 2-disjoint path cover of Johnson graphs |
| topic | Combinatorics Discrete Mathematics 05C38, 68R10 |
| url | https://arxiv.org/abs/2507.15463 |