Partition and Disjoint Cycles in Digraphs

被引:0
|
作者
Chunjiao Song
Jin Yan
机构
[1] Shandong University,School of Mathematics
来源
Graphs and Combinatorics | 2023年 / 39卷
关键词
Minimum out-degree; Partition; Vertex disjoint cycles; Probability method; 05C20; 05C38;
D O I
暂无
中图分类号
学科分类号
摘要
Let D be a digraph, we use δ+(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta ^+(D)$$\end{document} to denote the minimum out-degree of D. In 2006, Alon proposed a problem stating that if there exists an integer function F(d1,…,dk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(d_1, \ldots ,d_k)$$\end{document} for a digraph D such that if δ+(D)≥F(d1,…,dk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta ^{+}(D) \ge F(d_1, \ldots ,d_k)$$\end{document}, then V(D) can be partitioned into k parts V1,…,Vk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V_1,\ldots ,V_k$$\end{document} with δ+(D[Vi])≥di\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta ^{+}(D[V_i]) \ge d_i$$\end{document} for each i∈[k]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i \in [k]$$\end{document}, here D[Vi]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$D[V_i]$$\end{document} denotes the induced subdigraph of Vi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V_i$$\end{document}. We prove that F(d1,…,dk)≤2(d1+⋯+dk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(d_1, \ldots ,d_k) \le 2(d_1+\cdots +d_k)$$\end{document} under the condition that the maximum in-degree is bounded and lnk2<min{d1,⋯,dk}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{\ln k}{2} < \min \{d_1, \dots , d_k\}$$\end{document} by using Lovász Local Lemma. Furthermore, we show that some regular digraphs, and digraphs of small order can be partitioned into k parts such that both the minimum in-degree and the minimum out-degree of the digraph induced by each part are at least di\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d_i$$\end{document} for each i∈[k]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i \in [k]$$\end{document}. Based on the results above, we further give lower bounds of the minimum out-degree of some special class digraphs containing k vertex disjoint cycles of different lengths.
引用
收藏
相关论文
共 50 条
  • [31] On vertex-disjoint cycles and degree sum conditions
    Gould, Ronald J.
    Hirohata, Kazuhide
    Keller, Ariel
    DISCRETE MATHEMATICS, 2018, 341 (01) : 203 - 212
  • [32] Vertex-Disjoint Cycles of Different Lengths in Local Tournaments
    Hung, Le Xuan
    Tan, Ngo Dac
    GRAPHS AND COMBINATORICS, 2023, 39 (05)
  • [33] Vertex-disjoint double chorded cycles in bipartite graphs
    Gao, Yunshu
    Lin, Xiaoyao
    Wang, Hong
    DISCRETE MATHEMATICS, 2019, 342 (09) : 2482 - 2492
  • [34] Vertex-Disjoint Cycles of Different Lengths in Local Tournaments
    Le Xuan Hung
    Ngo Dac Tan
    Graphs and Combinatorics, 2023, 39
  • [35] Vertex-disjoint cycles of different lengths in multipartite tournaments
    Hung, Le Xuan
    Hieu, Do Duy
    Tan, Ngo Dac
    DISCRETE MATHEMATICS, 2022, 345 (06)
  • [36] Two disjoint cycles of various lengths in alternating group graph
    Cheng, Dongqin
    APPLIED MATHEMATICS AND COMPUTATION, 2022, 433
  • [37] Vertex-Disjoint Cycles of Order Eight with Chords in a Bipartite Graph
    Zou, Qingsong
    Chen, Hongyu
    Li, Guojun
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2013, 36 (01) : 255 - 262
  • [38] TOURNAMENTS AND BIPARTITE TOURNAMENTS WITHOUT VERTEX DISJOINT CYCLES OF DIFFERENT LENGTHS
    Ngo Dac Tan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (01) : 485 - 494
  • [39] Vertex-disjoint short cycles containing specified edges in a graph
    Matsumura, Hajime
    ARS COMBINATORIA, 2006, 80 : 147 - 152
  • [40] Covering vertices by a specified number of disjoint cycles, edges and isolated vertices
    Chiba, Shuya
    Fujita, Shinya
    DISCRETE MATHEMATICS, 2013, 313 (03) : 269 - 277