Degree sequence conditions for maximally edge-connected and super-edge-connected oriented graphs depending on the clique number

被引:0
|
作者
Volkmann, Lutz [1 ]
机构
[1] Rhein Westfal TH Aachen, Lehrstuhl Math 2, D-52056 Aachen, Germany
关键词
oriented graph; edge-connectivity; super-edge-connectivity; degree sequence; clique number; BIPARTITE DIGRAPHS; DIRECTED-GRAPHS;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
An orientation of a simple graph G is called an oriented graph. If D is an oriented graph, delta(D) its minimum degree and lambda(D) its edge-connectivity, then lambda(D) <= delta(D). The oriented graph is called maximally edge-connected if lambda(D) = delta(D) and super-edge-connected, if every minimum edge-cut is trivial. If D is an oriented graph with the property that the underlying graph G(D) contains no complete subgraph of order p + 1, then we say that the clique number omega(D) of D is less or equal p. In this paper we present degree sequence conditions for maximally edge-connected and super-edge-connected oriented graphs D with clique number omega(D) <= p for an integer p >= 2.
引用
收藏
页码:55 / 64
页数:10
相关论文
共 38 条
  • [21] Degree sequence conditions for equal edge-connectivity and minimum degree, depending on the clique number
    Volkmann, L
    JOURNAL OF GRAPH THEORY, 2003, 42 (03) : 234 - 245
  • [22] On the existence of super edge-connected graphs with prescribed degrees
    Tian, Yingzhi
    Meng, Jixiang
    Lai, Hongjian
    Zhang, Zhao
    DISCRETE MATHEMATICS, 2014, 328 : 36 - 41
  • [23] Super Edge-Connected Linear Hypergraphs
    Lin, Shangwei
    Pei, Jianfeng
    Li, Chunfang
    PARALLEL PROCESSING LETTERS, 2020, 30 (03)
  • [24] Sufficient conditions on the zeroth-order general Randic index for maximally edge-connected graphs
    Chen, Zhibing
    Su, Guifu
    Volkmann, Lutz
    DISCRETE APPLIED MATHEMATICS, 2017, 218 : 64 - 70
  • [25] Sufficient conditions for maximally restricted edge connected graphs
    Qin, Yingying
    Ou, Jianping
    DISCRETE MATHEMATICS, 2012, 312 (19) : 2969 - 2972
  • [26] Highly edge-connected detachments of graphs and digraphs
    Berg, AR
    Jackson, B
    Jordán, T
    JOURNAL OF GRAPH THEORY, 2003, 43 (01) : 67 - 77
  • [27] Maximally edge-connected graphs and Zeroth-order general RandiA‡ index for
    Su, Guifu
    Xiong, Liming
    Su, Xiaofeng
    Li, Guojun
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (01) : 182 - 195
  • [28] Minimally (k, k)-edge-connected graphs
    Hennayake, K
    Lai, HJ
    Li, DY
    Ma, JZ
    JOURNAL OF GRAPH THEORY, 2003, 44 (02) : 116 - 131
  • [29] The minimum restricted edge-connected graph and the minimum size of graphs with a given edge-degree
    Yang, Weihua
    Tian, Yingzhi
    Li, Hengzhe
    Li, Hao
    Guo, Xiaofeng
    DISCRETE APPLIED MATHEMATICS, 2014, 167 : 304 - 309
  • [30] Construction of super edge-connected multigraphs with prescribed degrees
    Cao, Xianglan
    Tian, Yingzhi
    Meng, Jixiang
    ARS COMBINATORIA, 2016, 127 : 3 - 13