Finite common coverings of graphs
Finite common coverings of graphs
复制标题
图的有限公共覆盖
DOI：
10.1016/0095-8956(82)90042-9
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
F. Leighton
中科院分区：
文献类型：
--
作者：
F. Leighton
很容易证明，当且仅当两个有限图具有相同的细化度时，它们有一个共同的（可能是无限的）覆盖。安格鲁因和加德纳（J. Combin）。Ser的理论。B30(1981), 184-187)证明了任何一对具有同价的正则图都有一个共同有限盖。更一般地说，他们推测任何具有相同细化度的图对都有一个共同的有限覆盖。本文验证了他们的猜想，并定义了一种构造任意具有相同细化度的图对的有限公共覆盖的方法。
It is easily shown that two finite graphs share a common (possibly infinite) cover if and only if they have the same degree refinement. Angluin and Gardiner (J. Combin. Theory Ser. B30(1981), 184–187) show that any pair of regular graphs with identical valence share a commonfinitecover. More generally, they conjecture thatanypair of graphs with the same degree refinement share a common finite cover. In this paper, their conjecture is verified and a method of constructing a finite common covering of any pair of graphs with the same degree refinement is defined.