×

Vertex-disjoint cycles containing specified vertices in a bipartite graph. (English) Zbl 1047.05033

Theorem. Let \(G\) be a graph of order \(n\), and suppose one of the following conditions is satisfied:
(1) \(n= 3k\) and \(\delta(G)\geq(7k- 2)/3\),
(2) \(3k+ 1\leq n\leq 4k\) and \(\delta(G)\geq(2n+ k- 3)/3\),
(3) \(4k\leq n\leq 6k- 2\) and \(\delta(G)\geq 3k-1\),
(4) \(n\geq 6k- 2\) and \(\delta(G)\geq n/2\).
Then for any distinct vertices \(v_1,v_2,\dots, v_k\), \(G\) can be partitioned into cycles \(C_1,C_2,\dots, C_k\) such that \(v_i\in V(C_i)\).
In this paper, the authors prove an analogous result for a bipartite graph.
Theorem. Suppose \(k\geq 1\), \(n\geq 4k- 2\), \(\delta(G)\geq (n+1)/2\), and \(v_1,v_2,\dots, v_k\) are distinct vertices of \(G\). Then either
(1) \(G\) can be partitioned into \(k\) cycles \(C_1,C_2,\dots, C_k\) such that \(v_i\in V(C_i)\), \(1\leq i\leq k\); or
(2) \(k= 2\) and \(G- \{v_1,v_2\}= 2K_{(n-1)/2,(n-1)/2}\). In particular, \(v_1\) and \(v_2\) belong to different partite sets. Moreover, if \(v_1\in V_1\), then \(V_2-\{v_2\}\subseteq N_G(v_1)\) and \(V_1- \{v_1\}\subseteq N_G(v_2)\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amar, J Graph Theory 20 pp 513– (1995)
[2] Brandt, J Graph Theory 24 pp 165– (1997)
[3] and Graphs & Digraphs, 3rd edition, Chapman & Hall, London, 1996.
[4] Chen, Aust J Combin 23 pp 37– (2001)
[5] Chen, Graphs and Combinatorics 16 pp 67– (2000)
[6] Dirac, Proc Lond Math Soc 2 pp 69– (1952)
[7] Egawa, J Graph Theory 43 pp 188– (2003)
[8] Egawa, Graphs and Combinatorics 16 pp 81– (2000)
[9] Enomoto, Combinatorica 18 pp 487– (1998)
[10] Moon, Israel J Math 1 pp 163– (1963)
[11] Ore, Am Math Monthly 67 pp 55– (1960)
[12] Wang, J Graph Theory 31 pp 101– (1999)
[13] Wang, J Graph Theory 31 pp 333– (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.