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 条
  • [41] Distance spectrum, 1-factor and vertex-disjoint cycles
    Zhang, Yuke
    Lin, Huiqiu
    Liu, Qinghai
    Zheng, Jinfeng
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 654 (10-27) : 10 - 27
  • [42] 2-connected Graph Partition Problems into Cycles
    Chen Lijuan
    PROCEEDINGS OF THE 2010 INTERNATIONAL CONFERENCE ON APPLICATION OF MATHEMATICS AND PHYSICS, VOL 2: ADVANCES ON APPLIED MATHEMATICS AND COMPUTATION MATHEMATICS, 2010, : 291 - 294
  • [43] Extremal spectral results of planar graphs without vertex-disjoint cycles
    Fang, Longfei
    Lin, Huiqiu
    Shi, Yongtang
    JOURNAL OF GRAPH THEORY, 2024, 106 (03) : 496 - 524
  • [44] Generalized Ramsey Numbers for Graphs with Three Disjoint Cycles Versus a Complete Graph
    Fujita, Shinya
    ELECTRONIC JOURNAL OF COMBINATORICS, 2012, 19 (02)
  • [45] Disjoint cycles and 2-factors with Fan-type condition in a graph
    Zhang, Jie
    Yan, Jin
    DISCRETE MATHEMATICS, 2022, 345 (04)
  • [46] Minimum degree conditions for vertex-disjoint even cycles in large graphs
    Chiba, Shuya
    Fujita, Shinya
    Kawarabayashi, Ken-ichi
    Sakuma, Tadashi
    ADVANCES IN APPLIED MATHEMATICS, 2014, 54 : 105 - 120
  • [47] Degree conditions for the partition of a graph into cycles, edges and isolated vertices
    Fujita, Shinya
    DISCRETE MATHEMATICS, 2009, 309 (11) : 3534 - 3540
  • [48] PAPR Reduction in OFDM Systems Based on Modified PTS Algorithm With Non-Disjoint Partition
    Chen, Houshou
    Wang, Jyun-Jie
    Tu, Cheng-En
    Chang, Hsiang-Wang
    2009 IEEE 20TH INTERNATIONAL SYMPOSIUM ON PERSONAL, INDOOR AND MOBILE RADIO COMMUNICATIONS, 2009, : 212 - 216
  • [49] Degree sum conditions for vertex-disjoint cycles passing through specified vertices
    Chiba, Shuya
    Yamashita, Tomoki
    DISCRETE MATHEMATICS, 2017, 340 (04) : 678 - 690
  • [50] Vertex-disjoint properly edge-colored cycles in edge-colored complete graphs
    Li, Ruonan
    Broersma, Hajo
    Zhang, Shenggui
    JOURNAL OF GRAPH THEORY, 2020, 94 (03) : 476 - 493