Premium
Solution of a conjecture of Volkmann on longest paths through an arc in strongly connected in‐tournaments
Author(s) -
Meierling Dirk
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20348
Subject(s) - tournament , combinatorics , conjecture , mathematics , arc (geometry) , vertex (graph theory) , order (exchange) , graph , path (computing) , discrete mathematics , geometry , computer science , finance , economics , programming language
An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. Let m = 4 or m = 5 and let D be a strongly connected in‐tournament of order ${{n}}\geq {{2}}{{m}}-{{2}}$ such that each arc belongs to a directed path of order at least m . In 2000, Volkmann showed that if D contains an arc e such that the longest directed path through e consists of exactly m vertices, then e is the only arc of D with that property. In this article we shall see that this proposition is true for ${{m}}\geq {{4}}$ , thereby validating a conjecture of Volkmann. Furthermore, we prove that if we ease the restrictions on the order of D to ${{n}}\geq {{2}}{{m}}-{{3}}$ , the in‐tournament D in question has at most two such arcs. In doing so, we also give a characterization of the in‐tournaments with exactly two such arcs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 130–148, 2009