tailieunhanh - Báo cáo toán hoc:"Vertex-oriented Hamilton cycles in directed graphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Vertex-oriented Hamilton cycles in directed graphs. | Vertex-oriented Hamilton cycles in directed graphs Michael J. Plantholt Department of Mathematics Illinois State University Normal IL 61790-4520 UsA mikep@ Shailesh K. Tipnis Department of Mathematics Illinois State University Normal IL 61790-4520 tipnis@ Submitted Feb 16 2009 Accepted Sep 12 2009 Published Sep 18 2009 Mathematics Subject Classifications 05C20 05C45 Abstract Let D be a directed graph of order n. An anti-directed Hamilton cycle H in D is a Hamilton cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D . We prove that if D is a directed graph with even order n and if the indegree and the outdegree of each vertex of D is at least 2n then D contains an anti-directed Hamilton cycle. This improves a bound of Grant 7 . Let V D P u Q be a partition of V D . a P Q vertex-oriented Hamilton cycle in D is a Hamilton cycle H in the graph underlying D such that for each v E P consecutive arcs of H incident on v do not form a directed path in D and for each v E Q consecutive arcs of H incident on v form a directed path in D. We give sufficient conditions for the existence of a P Q vertex-oriented Hamilton cycle in D for the cases when P In and when In P In. This sharpens a bound given by Badheka et al. in 1 . 1 Introduction Let G be a graph with vertex set V G and edge set E G . For a vertex v E V G the degree of v in G denoted by deg v G is the number of edges of G incident on v. Let J G minvey G deg v G . Let D be a directed graph with vertex set V D and arc set A D . For a vertex v E V D the outdegree respectively indegree of v in D denoted by d v D respectively d- v D is the number of arcs of D directed out of v respectively directed into v . Let Ỏ D minvey D min d v D d- v D . The graph underlying D is the graph obtained from D by ignoring the directions of the arcs of D. A directed Hamilton cycle H in D is a Hamilton cycle in the graph underlying D such that all pairs of consecutive arcs in H