首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On disjoint configurations in infinite graphs
Authors:Thomas Andreae
Abstract:For a graph A and a positive integer n, let nA denote the union of n disjoint copies of A; similarly, the union of ?0 disjoint copies of A is referred to as ?0A. It is shown that there exist (connected) graphs A and G such that nA is a minor of G for all n??, but ?0A is not a minor of G. This supplements previous examples showing that analogous statements are true if, instead of minors, isomorphic embeddings or topological minors are considered. The construction of A and G is based on the fact that there exist (infinite) graphs G1, G2,… such that Gi is not a minor of Gj for all ij. In contrast to previous examples concerning isomorphic embeddings and topological minors, the graphs A and G presented here are not locally finite. The following conjecture is suggested: for each locally finite connected graph A and each graph G, if nA is a minor of G for all n ? ?, then ?0A is a minor of G, too. If true, this would be a far‐reaching generalization of a classical result of R. Halin on families of disjoint one‐way infinite paths in graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 222–229, 2002; DOI 10.1002/jgt.10016
Keywords:maximum number of disjoint infinite paths in graphs  disjoint copies of a graph  minors  topological minors  isomorphic embeddings  locally finite graphs  well‐quasi‐ordering    Wagner’  s conjecture' for infinite graphs
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号