Metadata language
Title:
On pre-H amiltonian Cycles in Balanced BipartiteDigraphs ; О предгамильтоновых контуров в сбалансированныхдвудольных орграфах
Author:
Darbinyan Samvel ; Дарбинян Самвел
Type:
Uncontrolled Keywords:
Digraphs ; cycles ; Hamiltonian cycles ; Bipartite balanced digraph ; Pancyclic ; Even pancyclic
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
ISSN:
Language:
Volume:
URL:
Additional Information:
Affiliation:
Institute for Informatics and Automation Problems of NAS RA