Paired $(n-1)$-to-$(n-1)$ disjoint path covers in bipartite transposition-like graphs
| Title: | Paired $(n-1)$-to-$(n-1)$ disjoint path covers in bipartite transposition-like graphs |
|---|---|
| Authors: | Coleman, Anna, Fischberg, Gabrielle, Gong, Charles, Harrington, Joshua, Wong, Tony W. H. |
| Publication Year: | 2024 |
| Collection: | Mathematics |
| Subject Terms: | Mathematics - Combinatorics, 05C45, 05C70, 05C75 |
| More Details: | A paired $k$-to-$k$ disjoint path cover of a graph $G$ is a collection of pairwise disjoint path subgraphs $P_1,P_2,\dotsc,P_k$ such that each $P_i$ has prescribed vertices $s_i$ and $t_i$ as endpoints and the union of $P_1,P_2,\dotsc,P_k$ contains all vertices of $G$. In this paper, we introduce bipartite transposition-like graphs, which are inductively constructed from lower ranked bipartite transposition-like graphs. We show that every rank $n$ bipartite transposition-like graph $G$ admit a paired $(n-1)$-to-$(n-1)$ disjoint path cover for all choices of $S=\{s_1,s_2,\dotsc,s_{n-1}\}$ and $T=\{t_1,t_2,\dotsc,t_{n-1}\}$, provided that $S$ is in one partite set of $G$ and $T$ is in the other. |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2402.11381 |
| Accession Number: | edsarx.2402.11381 |
| Database: | arXiv |
Be the first to leave a comment!