华东师范大学学报(自然科学版) ›› 2016, Vol. 2016 ›› Issue (1): 91-95.doi: 10.3969/j.issn.1000-5641.2016.01.011

• 应用数学与基础数学 • 上一篇    下一篇

有向图的双超连通性

 李静静, 刘娟   

  1. 新疆师范大学~~数学科学学院, 乌鲁木齐 830054
  • 收稿日期:2015-01-16 出版日期:2016-01-25 发布日期:2016-03-10
  • 通讯作者: 刘娟, 女, 教授，研究方向为图论与组合数学. E-mail:liujuan1999@126.com.
  • 作者简介:李静静, 女, 硕士研究生,研究方向为图论与组合数学. E-mail: 804474119@qq.com.
  • 基金资助:

    基金项目: 国家自然科学基金~(61363020, 11301450);新疆维吾尔自治区青年科技创新人才培养工程(2013731011);
    新疆维吾尔自治区自然科学基金\,(2012211B21); 新疆研究生科技创新项目(2014118)

Bi-super-connected digraphs

 LI  Jing-Jing, LIU  Juan   

  • Received:2015-01-16 Online:2016-01-25 Published:2016-03-10

RichHTML

7

PDF

933

摘要： 简单有向图(无环与重弧),如果满足每个最小点割都是某个点的出邻点集或入邻点集,则称是超连通的. 在超连通有向图中,如果存在一个最小点割既是某个点的出邻点集又是某个点的入邻点集,则称是双超连通的. 主要研究了线图双超连通性的充要条件; 同时,研究了笛卡尔积与字典积的双超连通性.

关键词: 组合问题, 超连通, 双超连通性, 线图, 笛卡尔积

Abstract: A simple digraph D (without loops and multiple arcs) is said to be super-connected if every minimum vertex-cut is the out-neighbor set or in-neighbor set of a vertex. A super-connected digraph D is said to be bi-super-connected if there exists a minimum vertex-cut is both the out-neighbor set of a vertex and the in-neighbor set of a vertex. In this paper, we will give the necessary and sufficient conditions of line digraph is bi-super-connected, furthermore, we study the big super-connectivity of Cartesian product and lexicographic product of two digraphs.

Key words: combinatorial problems, super-connected;bi-super-connected, line digraphs, Cartesianproduct

中图分类号: