Partition of a directed bipartite graph into two directed cycles
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.
- A method in graph theory
- Covering the vertices of a digraph by cycles of prescribed length
- Graph theory
- scientific article; zbMATH DE number 825135 (Why is no real title available?)
- On circuits in graphs
- On the maximal number of independent circuits in a graph
- Partition of a bipartite graph into cycles
- Partition of a bipartite Hamiltonian graph into two cycles
- Partition of a bipartite Hamiltonian graph into two cycles
- On a conjecture on directed cycles in a directed bipartite graph
- Oriented bipartite graphs and the Goldbach graph
- The structure of 2-colored best match graphs
- Disjoint directed cycles with specified lengths in directed bipartite graphs
- Partitioning a graph into two square-cycles
- scientific article; zbMATH DE number 2188348 (Why is no real title available?)
- Partition of a bipartite graph into cycles
This page was built for publication: Partition of a directed bipartite graph into two directed cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126308)
