Անվանում:
On Hamiltonian Bypasses in Digraphs with the Condition ofY. Manoussakis
Հեղինակ:
Տեսակ:
Չվերահսկվող բանալի բառեր:
Digraphs ; cycles ; Hamiltonian cycles ; Hamiltonian bypasses
Ամփոփում:
Let D be a strongly connected directed graph of order n > 4 which satisfies the following condition for every triple x, y, z of vertices such that x and y are nonadjacent: If there is no arc from x to z, then d(x) + d(y) + d+ (x) + d- (z) > 3n — 2. If there is no arc from z to x, then d(x) + d(y) + d- (x) + d+(z) > 3n — 2. In [15] (J. of Graph Theory, 16(5), 51-59, 1992) Y. Manoussakis proved that D is Hamiltonian. In [9] it was shown that D contains a pre-Hamiltonian cycle (i.e., a cycle of length n — 1) or n is even and D is isomorphic to the complete bipartite digraph with partite sets of cardinalities of n/2 and n/2. In this paper we show that D contains also a Hamiltonian bypass (i.e., a subdigraph is obtained from a Hamiltonian cycle by reversing exactly one arc) or D is isomorphic to one tournament of order five.
Լեզու:
URL:
լրացուցիչ տեղեկատվություն:
Կազմակերպության անվանում:
Institute for Informatics and Automation Problems
Երկիր:
Տարի:
Ժամանակահատված:
Գիտաժողովի անվանում:
10 th International Conference on Computer Science and Information Technologies CSIT 2015