НАН РА. Математические вопросы кибернетики и вычислительной техники=Mathematical problems of computer science

On a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs

Darbinyan, Samvel Kh. and Karapetyan, Iskandar A. (2018) On a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs. Математические вопросы кибернетики и вычислительной техники, № 49. pp. 26-34. ISSN 0131-4645

[img]
Preview
PDF
Download (355Kb) | Preview

    Abstract

    R. Wang (Discrete Mathematics and Theoretical Computer Science, vol. 19(3), 2017) proposed the following problem. Problem. Let D be a strongly connected balanced bipartite directed graph of order 2a≥8. Suppose that d(x)≥ 2a-k, d(y) ≥a+k or d(y)≥2a-k, d(x)≥a+k for every pair of vertices fx; yg with a common out-neighbour, where 2≤k≤a/2. Is D Hamiltonian? In this paper, we prove that if a digraph D satisfies the conditions of this problem, then (i) D contains a cycle factor, (ii) for every vertex x € V (D) there exists a vertex y € V (D) such that x and y have a common out-neighbour.

    Item Type: Article
    Additional Information: Կողմնորոշված երկմասնյա գրաֆի համիլտոնյանության վերաբերյալ Վանգի խնդրի մասին / Ս. Դարբինյան, Ի. Կարապետյան: О задаче Ванга о гамильтоновости двудольных орграфов / С. Дарбинян, И. Карапетян
    Uncontrolled Keywords: Digraph, cycle, Hamiltonian cycle, Bipartite balanced digraph, Perfect matching.
    Subjects: Q Science > QA Mathematics > Graph theory
    Divisions: UNSPECIFIED
    Depositing User: FSL Bibl. Dept.
    Date Deposited: 22 Oct 2018 15:17
    Last Modified: 25 Oct 2018 11:23
    URI: http://compsci.asj-oa.am/id/eprint/897

    Actions (login required)

    View Item