A monotone path in an edge-ordered graph
type: Item
instance of: scholarly article
title: A monotone path in an edge-ordered graph
zbMATH Open document ID: 0633.05043
DOI: 10.1155/S0161171287000383
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 1987-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/46238
review text: An edge-ordered graph is an ordered pair (G,f), where G is a graph and f is a bijective function, f: E(G)\(\to \{1,2,...,| E(G)| \}\). A monotone path of length k in (G,f) is a simple path \(P_{k+1}:\) \(v_ 1v_ 2...v_{k+1}\) in G such that either \(f(\{v_ i,v_{i+1}\})<f(\{v_{i+1},v_{i+2}\})\) or \(f(\{v_ i,v_{+1}\})>f(\{v_{i+1},v_ i\})\) 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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 4029613
zbMATH Keywords: edge-ordered graph
zbMATH Keywords: monotone path
author: Arie Bialostocki
author: Yehuda Roditty
MaRDI profile type: Publication
OpenAlex ID: W2068000777
description: scientific article; zbMATH DE number 4029613