Disjoint path covers of star graphs

Hongwei Qiao and Jixiang Meng

Applied Mathematics and Computation, 2025, vol. 487, issue C

Abstract: Given a graph G, let S and T be two vertex-disjoint subsets of equal size k of G. A k-disjoint path cover of G corresponding to S and T is the union of k vertex-disjoint paths among S and T that spans G. If every vertex of S should be joined to a prescribed vertex in T, it is defined to be paired, otherwise it is unpaired. Let STn be a star graph with bipartition V0 and V1. Let S⊆V0 and T⊆V1 be two vertex subsets of equal size k. It is shown in this paper that STn admits an unpaired k-disjoint path cover between S and T, where k≤n−2 and n≥4. In view of the degree of STn, this result is optimal.

Keywords: Star graph; Disjoint path cover; Hamiltonian path (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300324005599
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:487:y:2025:i:c:s0096300324005599

DOI: 10.1016/j.amc.2024.129098

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().