Object

Title: On pre-Hamiltonian Cycles in Hamiltonian Digraphs ; О предгамильтоновых контурах в гамильтоновыхориентированных графах

Abstract:

Let D be a strongly connected directed graph of order n ≥¸ 4. In [14] (J. of Graph Theory, Vol.16, No. 5, 51-59, 1992) Y. Manoussakis proved the following theorem: Suppose that D satis¯es 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. Then D is Hamiltonian. In this paper we show that: If D satis¯es the condition of Manoussakis' theorem, then 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 n/2 and n/2.
; Ориентированный контур, который содержит все вершины ориентированного графа (орграфа), называется предгамильтоновым контуром. В работе доказано, что любой орграф, который удовлетворяет достаточному условию гамильтоновости орграфов Маноусакиса (J. of Graph Theory 16(1) (1992) 51-59), содержит предгамильтоновый контур или является двудольным балансированным полным орграфом.

Date submitted:

16.10.2014

Date accepted:

27.01.2015

Identifier:

oai:noad.sci.am:136014

ISSN:

0131-4645

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

43

URL:


Additional Information:

samdarbin@ipia.sci.am ; isko@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems

Country:

Armenia

Indexing:

ASCI

Object collections:

Last modified:

Mar 4, 2021

In our library since:

Jul 29, 2020

Number of object content hits:

18

All available object's versions:

https://noad.sci.am/publication/149634

Show description in RDF format:

RDF

Show description in OAI-PMH format:

OAI-PMH

This page uses 'cookies'. More information