Chalopin, J. and Paulusma, Daniel (2014) 'Packing bipartite graphs with covers of complete bipartite graphs.', Discrete applied mathematics., 168 . pp. 40-50.
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.
|Keywords:||Bipartite graph, Graph factor, Locally bijective homomorphism, Pseudo-covering.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (864Kb)
|Full text:||(VoR) Version of Record|
Download PDF (385Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/j.dam.2012.08.026|
|Date accepted:||No date available|
|Date deposited:||17 April 2013|
|Date of first online publication:||May 2014|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|