Skip to main content

Research Repository

Advanced Search

Packing bipartite graphs with covers of complete bipartite graphs

Chalopin, J.; Paulusma, D.

Packing bipartite graphs with covers of complete bipartite graphs Thumbnail


Authors

J. Chalopin



Abstract

For a set SS of graphs, a perfect SS-packing (SS-factor) of a graph GG is a set of mutually vertex-disjoint subgraphs of GG that each are isomorphic to a member of SS and that together contain all vertices of GG. If GG allows a covering (locally bijective homomorphism) to a graph HH, i.e., a vertex mapping f:VG→VHf:VG→VH satisfying the property that f(u)f(v)f(u)f(v) belongs to EHEH whenever the edge uvuv belongs to EGEG such that for every u∈VGu∈VG the restriction of ff to the neighborhood of uu is bijective, then GG is an HH-cover. For some fixed HH let S(H)S(H) consist of all connected HH-covers. Let Kk,ℓKk,ℓ be the complete bipartite graph with partition classes of size kk and ℓℓ, respectively. For all fixed k,ℓ≥1k,ℓ≥1, we determine the computational complexity of the problem that tests whether a given bipartite graph has a perfect S(Kk,ℓ)S(Kk,ℓ)-packing. Our technique is partially based on exploring a close relationship to pseudo-coverings. A pseudo-covering from a graph GG to a graph HH is a homomorphism from GG to HH that becomes a covering to HH when restricted to a spanning subgraph of GG. We settle the computational complexity of the problem that asks whether a graph allows a pseudo-covering to Kk,ℓKk,ℓ for all fixed k,ℓ≥1k,ℓ≥1.

Citation

Chalopin, J., & Paulusma, D. (2014). Packing bipartite graphs with covers of complete bipartite graphs. Discrete Applied Mathematics, 168, 40-50. https://doi.org/10.1016/j.dam.2012.08.026

Journal Article Type Article
Publication Date May 1, 2014
Deposit Date Mar 11, 2013
Publicly Available Date Mar 29, 2024
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 168
Pages 40-50
DOI https://doi.org/10.1016/j.dam.2012.08.026
Keywords Bipartite graph, Graph factor, Locally bijective homomorphism, Pseudo-covering.
Public URL https://durham-repository.worktribe.com/output/1487695

Files






You might also like



Downloadable Citations