Premium
Locally semicomplete digraphs that are complementary m ‐pancyclic
Author(s) -
Guo Yubao,
Volkmann Lutz
Publication year - 1996
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/(sici)1097-0118(199602)21:2<121::aid-jgt2>3.0.co;2-t
Subject(s) - combinatorics , mathematics , digraph , disjoint sets , vertex (graph theory) , integer (computer science) , discrete mathematics , graph , computer science , programming language
If A and B are two subdigraphs of D , then we denote by d D ( A, B ) the distance between A and B . Let D be a 2‐connected locally semicomplete digraph on n ≥ 6 vertices. If S is a minimum separating set of D and$$d=\min\{d_{D-S}(N^{+}(s)-S, N^{-}(s)-S)\,\mid\,s\in S\},$$ then m = max{3, d + 2} ≤ n /2 and D contains two vertex‐disjoint dicycles of lengths t and n − t for every integer t satisfying m ≤ t ≤ n /2, unless D is a member of a family of locally semicomplete digraphs. This result extends those of Reid ( Ann. Discrete Math. 27 (1985), 321–334) and Song ( J. Combin. Theory B 57 (1993), 18–25) for tournaments, and it confirms two conjectures of Bang‐Jensen ( Discrete Math. 100 (1992), 243–265. © 1996 John Wiley & Sons, Inc.