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
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      4 August 2004
      0 references
      bipartite graph
      0 references
      2-factor
      0 references
      minimum degree
      0 references
      cycles
      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

      Identifiers