Báo cáo toán học: "A Traceability Conjecture for Oriented Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A Traceability Conjecture for Oriented Graphs. | A Traceability Conjecture for Oriented Graphs Marietjie Frick and Susan A van Aardty Department of Mathematical Sciences University of South Africa South Africa frickm vaardsag@ Jean E Dunbar Converse College South Carolina USA Morten H Nielsen and Ortrud R Oellermannz Department of Mathematics and Statistics University of Winnipeg Canada Submitted Jan 26 2007 Accepted Nov 20 2008 Published Dec 9 2008 Mathematics Subject Classihcation 05C20 05C38 05C15 Abstract A di graph G of order n is k-traceable for some k 1 k n if every induced sub di graph of G of order k is traceable. It follows from Dirac s degree condition for hamiltonicity that for k 2 every k-traceable graph of order at least 2k 1 is hamiltonian. The same is true for strong oriented graphs when k 2 3 4 but not when k 5. However we conjecture that for k 2 every k-traceable oriented graph of order at least 2k 1 is traceable. The truth of this conjecture would imply the truth of an important special case of the Path Partition Conjecture for Oriented Graphs. In this paper we show the conjecture is true for k 5 and for certain classes of graphs. In addition we show that every strong k-traceable oriented graph of order at least 6k 20 is traceable. We also characterize those graphs for which all walkable orientations are k-traceable. Keywords Longest path oriented graph k-traceable Path Partition Conjecture Traceability Conjecture. Supported by the National Research Foundation under Grant number 2053752 ySupported by the National Research Foundation under Grant number TTK2004080300021 Supported by an NSERC grant CANADA. This work was completed in part at a BIRS Workshop 06rit126 THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R150 1 1 Introduction Let G be a finite simple graph with vertex set V G and edge set E G . The number of vertices of G is called its order and the number of edges is called its size and are denoted by n G and m G .