Paired (n-1)-to-(n-1) disjoint path covers in bipartite transposition-like graphs

2024/02/17 by Anna Coleman, Coleman, Anna, Gabrielle Fischberg +7
Biochemistry, Genetics and Molecular Biology · Engineering · #05C45 #05C70 #05C75 #Combinatorics (math.CO) #FOS: Mathematics #Genome Rearrangement Algorithms #Optimization and Packing Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2402.11381

openalex publication_date 2024/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A paired k-to-k disjoint path cover of a graph G is a collection of pairwise disjoint path subgraphs P₁,P₂,\dotsc,P_k such that each P_i has prescribed vertices s_i and t_i as endpoints and the union of P₁,P₂,\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₁,s₂,\dotsc,s_n-1\ and T=\t₁,t₂,\dotsc,t_n-1\, provided that S is in one partite set of G and T is in the other.

Related

• Paired many-to-many 2-disjoint path cover of Johnson graphs
• A Hall-type condition for path covers in bipartite graphs
• Unpaired many-to-many disjoint path cover of balanced hypercubes
• Two Disjoint Alternating Paths in Bipartite Graphs
• On the Two Paths Theorem and the Two Disjoint Paths Problem