International Journal of Mathematics and Mathematical Sciences
Volume 10 (1987), Issue 2, Pages 315-320
doi:10.1155/S0161171287000383
A monotone path in an edge-ordered graph
1Department of Mathematics and Applied Statistics, University of Idaho, Moscow 83843, Idaho, USA
2School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978, Israel
Received 8 January 1986; Revised 23 September 1986
Copyright © 1987 A. Bialostocki and Y. Roditty. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
An edge-ordered graph is an ordered pair (G,f), where G is a graph and f is a bijective function, f:E(G)→{1,2,…,|E(G)|}. A monotone path of length k in (G,f) is a simple path Pk+1:v1v2…vk+1 in G such that either f({vi,vi+1})<f({vi+1,vi+2}) or f({vi,vi+1})>f({vi+1,vi}) for i=1,2,…,k−1.
It is proved that a graph G has the property that (G,f) contains a monotone path of length three for every f iff G contains as a subgraph, an odd cycle of length at least five or one of six listed graphs.