Premium
Interminable Paths and Trails: Extreme Cases
Author(s) -
Dirac G. A.
Publication year - 1978
Publication title -
mathematische nachrichten
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.913
H-Index - 50
eISSN - 1522-2616
pISSN - 0025-584X
DOI - 10.1002/mana.19780820102
Subject(s) - notation , multiplicity (mathematics) , terminology , combinatorics , mathematics , graph , path (computing) , discrete mathematics , computer science , philosophy , geometry , linguistics , arithmetic , programming language
Abstract This paper is concerned with terminable and interminable paths and trails in infinite graphs. It is shown that The only connected graphs which contain no 2 – ∞ way and in which no finite path is terminable are precisely all the 1 – ∞ multiways. The only connected graphs which have no 2 – ∞ trail and in which no finite trail is terminable are precisely all the 1 – ∞ multiways all of whose multiplicities are odd numbers and which have infinitely many bridges. In addition the strucuture of those connected graphs is determined which have a 1 – ∞ trail and in which no 1 – ∞ trail but every finite trail is terminable. In this paper the terminology and notation of a previous paper of the writer [1] and of F. H ARARY 's book [6] will be used. Furthermore, a graph consisting of the distinct nodes n 1 ,…, n δ (where δ≧1) and of one or more ( n i , n i +1 )‐edges for i = 1,…, δ – 1 will be called a multiway , and analogously for 1 – ∞ and 2 – ∞ multiways. The number of edges joining n i and n i +1 will be called the ( n i ,+1 )‐ multiplicity . Thus a multiway in which each multiplicity is 1 is a way. Multiplicities are allowed to be infinite.