Packing bipartite graphs with covers of complete bipartite graphs
Packing bipartite graphs with covers of complete bipartite graphs
复制标题
用完整二分图的覆盖来包装二分图
DOI：
10.1016/j.dam.2012.08.026
复制
发表时间：
2014
影响因子：
1.1
通讯作者：
Chalopin J
中科院分区：
文献类型：
--
作者：
Chalopin J
对于图的集合S，图G的完美S-填充（S-因子）是G的一组顶点不相交的子图，每个子图同构于S的一个成员，并且它们包含G的所有顶点。如果G允许图H的覆盖（局部双射同态），即顶点映射f：VG → VH满足f（u）f（v）属于EH的性质，只要边uv属于EG，使得对任意u∈ VG，f到u的邻域的限制是双射的，则G是H-覆盖。对于某个固定的H，设S（H）由所有连通的H-覆盖组成。设Kk，k是划分类分别为k和k的完全二部图.对于所有固定的k，n ≥ 1，我们确定了测试给定二部图是否有完美S（Kk，n）-填充问题的计算复杂性.我们的技术部分是基于探索伪覆盖的密切关系。从图G到图H的伪覆盖是从G到H的同态，当限制到G的一个生成子图时，该同态成为到H的覆盖。我们解决了一个问题的计算复杂性，这个问题是问一个图是否允许一个伪覆盖到Kk，k ≥ 1。
For a set S of graphs, a perfect S-packing (S-factor) of a graph G is a set of mutually vertex-disjoint subgraphs of G that each are isomorphic to a member of S and that together contain all vertices of G. If G allows a covering (locally bijective homomorphism) to a graph H, ie, a vertex mapping f: V G→ V H satisfying the property that f (u) f (v) belongs to E H whenever the edge u v belongs to E G such that for every u∈ V G the restriction of f to the neighborhood of u is bijective, then G is an H-cover. For some fixed H let S (H) consist of all connected H-covers. Let K k, ℓ be the complete bipartite graph with partition classes of size k and ℓ, respectively. For all fixed k, ℓ≥ 1, we determine the computational complexity of the problem that tests whether a given bipartite graph has a perfect S (K k, ℓ)-packing. Our technique is partially based on exploring a close relationship to pseudo-coverings. A pseudo-covering from a graph G to a graph H is a homomorphism from G to H that becomes a covering to H when restricted to a spanning subgraph of G. We settle the computational complexity of the problem that asks whether a graph allows a pseudo-covering to K k, ℓ for all fixed k, ℓ≥ 1.
登录
查看更多内容
从分布式计算模型派生的图标签：完整的复杂性分类
影响因子：
2.1
作者：
Jérémie Chalopin;D. Paulusma
通讯作者：
D. Paulusma
从分布式计算模型派生的图标签
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
emie Chalopin;D. Paulusma
通讯作者：
D. Paulusma
影响因子：
1.1
作者：
J. Fiala;D. Paulusma
通讯作者：
D. Paulusma
关于覆盖有限复数的复杂性和组合学
DOI：
--
发表时间：
1991
期刊：
The Australasian Journal of Combinatorics
影响因子：
--
作者：
J. Abello;M. Fellows;J. Stillwell
通讯作者：
J. Stillwell
关于图覆盖问题的复杂性
DOI：
--
发表时间：
1998
期刊：
Nordic Journal of Computing
影响因子：
--
作者：
Jan Kratochvíl;A. Proskurowski;J. A. Telle
通讯作者：
J. A. Telle