Ամսագրի կամ հրապարակման վերնագիր:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Հրապարակման ամսաթիւ:

2014

Հատոր:

41

ISSN:

0131-4645

Լրացուցիչ տեղեկութիւն:

կապին հետեւելուն համար սեղմէ հոս

Այլ վերնագիր:

Կողմնորոշված համիլտոնյան գրաֆների մի դասի համիլտոնյան շրջանցումների մասին; О гамильтоновых обходах в одном классе гамильтоновых орграфов

Ծածկոյթ:

23-37

Ամփոփում:

Let D be a strongly connected directed graph of order n ¸ 4 which satis¯es the following condition (*): for every pair of non-adjacent vertices x; y with a common in-neighbour d(x) + d(y) ¸ 2n ¡ 1 and minfd(x); d(y)g ¸ n ¡ 1. In [2] (J. of Graph Theory 22 (2) (1996) 181-187)) J. Bang-Jensen, G. Gutin and H. Li proved that D is Hamiltonian. In [9] it was shown that if D satis¯es the condition (*) and the minimum semi-degree of D at least two, then either D contains a pre-Hamiltonian cycle (i.e., a cycle of length n ¡ 1) or n is even and D is isomorphic to complete bipartite digraph (or to complete bipartite digraph minus one arc) with equal partite sets. In this paper we show that if the minimum out-degree of D at least two and the minimum in-degree of D at least three, then D contains also a Hamiltonian bypass, (i.e., a subdigraph is obtained from a Hamiltonian cycle by reversing exactly one arc). Keywords: Digraphs, Cycles, Hamiltonian cycles, Hamiltonian bypasses.

Հրատարակիչ:

АН Арм. ССР

Ստեղծման ամսաթիւը:

2014-09-10

Ձեւաչափ:

pdf

Նոյնացուցիչ:

oai:arar.sci.am:258800

Բնօրինակին գտնուելու վայրը:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան