A monotone path in an edge-ordered graph

A. Bialostocki and Y. Roditty

International Journal of Mathematics and Mathematical Sciences, 1987, vol. 10, 1-6

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 P k + 1 : v 1 v 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 i + 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.

Date: 1987
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/IJMMS/10/803136.pdf (application/pdf)
http://downloads.hindawi.com/journals/IJMMS/10/803136.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jijmms:803136

DOI: 10.1155/S0161171287000383

Access Statistics for this article

More articles in International Journal of Mathematics and Mathematical Sciences from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().