Which graphs allow infinite nonrepetitive walks? (Q2639070)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Which graphs allow infinite nonrepetitive walks? |
scientific article |
Statements
Which graphs allow infinite nonrepetitive walks? (English)
0 references
1991
0 references
An infinite walk in a graph G is an infinite sequence of vertices \(W=a_ 1a_ 2...a_ n..\). such that for each i, \(a_ ia_{i+1}\) is an edge of G. The walk W is nonrepetitive if W cannot be expressed as the concatenation of walks \(W_ 1W_ 2W_ 2W_ 3\) where the duplicated walk \(W_ 2\) is not trivial. It is shown that all connected graphs, except for paths with 4 or less vertices, have nonrepetitive infinite walks. This is equivalent to showing that a graph G has a nonrepetitive infinite walk if and only if G has a minor isomorphic to \(P_ 5\), \(C_ 3\), or \(K_{1,3}\).
0 references
nonrepetitive infinite walks
0 references