Abstract:

Let D be a strongly connected balanced bipartite directed graph of order 2a ¸ 10. Let x; y be distinct vertices in D. fx; yg dominates a vertex z if x ! z and y ! z; in this case, we call the pair fx; yg dominating. In this paper we prove: If maxfd(x); d(y)g ¸ 2a¡2 for every dominating pair of vertices fx; yg, then either the underlying graph of D is 2-connected or D contains a cycle of length 2a ¡ 2 or D is isomorphic to one digraph of order ten.
; Ориентированный контур проходящий через все вершины сбалансированного двудольного орграфа, кроме двух вершин, называется предгамильтоновым контуром. В настоящей статье доказывается: Теорема: Пусть Б - 2а-вершинный (а > 5) сбалансированный двудольный орграф. Если для любых доминирующих пар вершин по крайней мере одна вершина имеет локальную степень не меньше чем 2а — 2, то Б содержит предгамильтоновый контур или неориентированная основа граф орграфа является Б 2-связной или Б изоморфен одному орграфу с десятью вершинами.

Publisher:

Mathematical Problems of Computer Science

Identifier:

oai:noad.sci.am:136050

ISSN:

0131-4645

Language:

English

Volume:

46

URL:

click here to follow the link

Additional Information:

samdarbin@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems of NAS RA

Country:

Armenia

Year:

2016

Indexing:

ASCI