华东师范大学学报（自然科学版） >

2016 , Vol. 2016 >Issue 1: 91 - 95

DOI: https://doi.org/10.3969/j.issn.1000-5641.2016.01.011

应用数学与基础数学

有向图的双超连通性

  • 李静静 ,
  • 刘娟
展开
  • 新疆师范大学~~数学科学学院, 乌鲁木齐 830054
李静静, 女, 硕士研究生,研究方向为图论与组合数学. E-mail: 804474119@qq.com.

收稿日期: 2015-01-16

  网络出版日期: 2016-03-10

基金资助

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

收起

Bi-super-connected digraphs

  • LI Jing-Jing ,
  • LIU Juan
Expand

Received date: 2015-01-16

  Online published: 2016-03-10

Fold

摘要

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

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

本文引用格式

李静静 , 刘娟 . 有向图的双超连通性[J]. 华东师范大学学报（自然科学版）, 2016 , 2016(1) : 91 -95 . DOI: 10.3969/j.issn.1000-5641.2016.01.011

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

参考文献

[1]MENG J X, ZHANG Z. Super-connected arc-transitive digraphs [J].Discrete Applied Mathematics, 2009, 157: 653-658.
[2]CHIUE W S, SHIEH B S. On connectivity of the Cartesian product oftwo graphs [J]. Applied Mathematics and Computation, 1999, 102:

129-137.
[3]XU J M, YANG C. Connectivity of Cartesian product graphs [J].Discrete Mathematics, 2006, 306: 159-165.
[4]MENG J X. Superconnectivity and super edge-connectivity of linegraphs [J]. Graph Theory Notes of New York, XL 2001: 12-14.
[5]XU J M, LV M, MA M J, HElLLWIG A. Super connectivity of line graphs[J]. Information Processing Letters, 2005, 94: 191-195.
[6]ZHANG Z, LIU F X, MENG J X. Super-connected $n$-th interated linedigraphs [J]. OR Transanctions, 2005, 9: 35-39.
[7]SHIEH B S. Super edge- and point-connectivities of the Cartesianproduct of regular graphs [J]. Networks, 2002, 40: 91-96.
[8]LIU J, MENG J X. Super-connected and super-arc-connected Cartesianproduct of digraphs [J]. Information Processing Letters, 2008, 108:

90-93.
[9]LIU J, MENG J X, ZHANG Z. Double-super-connected digraph [J].Discrete Applied Mathematics, 2010, 158: 1012-1016.
[10]XU J M. Topological Structure and Analysis of InterconnectionNetworks [M]. Dordrecht, Netherlands: Kluwer Academic Publishers,

2001.
Options
文章导航

/

〈 〉