Minimal Degree and (k, m)-Pancyclic Ordered Graphs

Given positive integers k less than or equal to m less than or equal to n, a graph G of order n is (k,m)-pancyclic ordered if for any set of k vertices of G and any integer r with m less than or equal to r less than or equal to n, there is a cycle of length r encountering the k vertices in a specifi...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2005-06, Vol.21 (2), p.197-211
Main Authors: Faudree, Ralph J., Gould, Ronald J., Jacobson, Michael S., Lesniak, Linda
Format: Article
Language:English
Subjects:
Graph algorithms
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given positive integers k less than or equal to m less than or equal to n, a graph G of order n is (k,m)-pancyclic ordered if for any set of k vertices of G and any integer r with m less than or equal to r less than or equal to n, there is a cycle of length r encountering the k vertices in a specified order. Minimum degree conditions that imply a graph of sufficiently large order n is (k,m)-pancylic ordered are proved. Examples showing that these constraints are best possible are also provided. [PUBLICATION ABSTRACT]
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-005-0604-5