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


Terminable and interminable paths and trails in infinite graphs
Authors:GA Dirac
Institution:Matematisk Institut, Aarhus Universitet, Nv. Munkegade, Aarhus, Denmark.
Abstract:The paper is concerned with certain kinds of random processes in infinite graphs. A finite trail of a graph which cannot be continued from either end is called terminated, and a finite trail is called terminable of it is a segment of a finite terminated trail; analogously for 1 - ∞ trails, finite paths, and 1 - ∞ paths.For k = 1,2,3,…, there exist graphs which contain 2 - ∞ paths and have node-connectivity k and in which no finite path and no 1 - ∞ path is terminable, and also such graphs in which every finite path and every 1 - ∞ path is terminable. In any graph with infinite node-connectivity every node of valency N0 is the end-node of terminated 1 - ∞ paths. There exist graphs with node-connectivity N0 in which every 1 - ∞ path is terminable. For λ = 1,2,3,…, there exist graphs which contain 2 - ∞ paths and have edge-connectivity λ and in which no finite trail and no 1 - ∞ trail is terminable, and also such graphs in which every finite trail and every 1 - ∞ trail is terminable. In contrast to the situation for 1 - ∞ paths, every connected infinite graph in which every 1 - ∞ trail is terminable contains at least one node of odd edge-degree and if in addition every finite trail is terminable, then there are at least two nodes of odd edge-degree.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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