Partition of a directed bipartite graph into two directed cycles
type: Item
instance of: scholarly article
title: Partition of a directed bipartite graph into two directed cycles
zbMATH Open document ID: 0880.05068
DOI: 10.1016/0012-365X(95)00165-S
author: Hong Wang
author: Charles Little
author: K. L. Teo
published in: Discrete Mathematics
publication date: 1998-01-19T00:00:00Z
review text: The main result is the following theorem: Let \(D=(V_1,V_2; A)\) be a directed bipartite graph with \(|V_1|=|V_2|= n\geq 2\). Suppose that \(d_D(x)+ d_D(y)\geq 3n+1\) for all \(x\in V_1\) and \(y\in V_2\). (\(d_D(x)\) denotes the number of vertices which are joined with the vertex \(x\) with an arc outgoing from \(x\) or incoming in \(x\).) Then \(D\) contains two vertex-disjoint directed cycles of lengths \(2n_1\) and \(2n_2\) respectively, for any positive integer partition \(n= n_1+n_2\). A bipartite graph which shows that the condition is sharp for even \(n\) and nearly sharp for odd \(n\) is constructed. The authors use several lemmas. Two of them were proved by \textit{J. A. Bondy} and \textit{V. Chvátal} [Discrete Math. 15, 111-135 (1976; Zbl 0331.05138)]. The second of these lemmas reads: If \(d_G(x)+ d_G(y)\geq n+1\) for any two non-adjacent vertices \(x\in V_1\) and \(y\in V_2\) of a nonoriented bipartite graph \(G=(V_1,V_2)\), then \(G\) is Hamiltonian.
reviewed by: M.Koman
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 955166
zbMATH Keywords: directed bipartite graph
zbMATH Keywords: cycles
zbMATH Keywords: partition
MaRDI profile type: Publication
cites work: Partition of a bipartite Hamiltonian graph into two cycles
cites work: Covering the vertices of a digraph by cycles of prescribed length
cites work: A method in graph theory
cites work: Q5422499
cites work: On the maximal number of independent circuits in a graph
cites work: On circuits in graphs
cites work: Q4858150
cites work: Partition of a bipartite graph into cycles
full work available at URL: 0012-365x(95)00165-s
OpenAlex ID: W2020341293
description: scientific article; zbMATH DE number 955166