Vertex-disjoint cycles containing specified vertices in a bipartite graph (Q4474280)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2081213
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Vertex-disjoint cycles containing specified vertices in a bipartite graph |
scientific article; zbMATH DE number 2081213 |
Statements
Vertex-disjoint cycles containing specified vertices in a bipartite graph (English)
0 references
4 August 2004
0 references
bipartite graph
0 references
2-factor
0 references
minimum degree
0 references
cycles
0 references
0.9191766381263732
0 references
0.8910269737243652
0 references
0.8904867172241211
0 references
0.8889333009719849
0 references
0.8886171579360962
0 references
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)\).
0 references