Packing bipartite graphs with covers of complete bipartite graphs

Chalopin, J.; Paulusma, D.

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: Apr 17, 2013
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• 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