有向图的双超连通性

李静静; 刘娟

doi:10.3969/j.issn.1000-5641.2016.01.011

有向图的双超连通性

doi: 10.3969/j.issn.1000-5641.2016.01.011

李静静,
刘娟^,

1.
新疆师范大学~~数学科学学院, 乌鲁木齐 830054

基金项目:

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

详细信息

作者简介:
李静静, 女, 硕士研究生,研究方向为图论与组合数学. E-mail: 804474119@qq.com.

通讯作者:
刘娟, 女, 教授，研究方向为图论与组合数学.

中图分类号: O157
计量
- 文章访问数: 769
- HTML全文浏览量: 34
- PDF下载量: 780
- 被引次数: 0
出版历程
- 收稿日期: 2015-01-16
- 刊出日期: 2016-01-25

Bi-super-connected digraphs

LI Jing-Jing,
LIU Juan^,

摘要

摘要: 简单有向图(无环与重弧),如果满足每个最小点割都是某个点的出邻点集或入邻点集,则称是超连通的. 在超连通有向图中,如果存在一个最小点割既是某个点的出邻点集又是某个点的入邻点集,则称是双超连通的. 主要研究了线图双超连通性的充要条件; 同时,研究了笛卡尔积与字典积的双超连通性.
- 组合问题 /
- 超连通 /
- 双超连通性 /
- 线图 /
- 笛卡尔积
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.
- combinatorial problems super-connectedbi-super-connected line digraphs Cartesianproduct /

HTML全文

参考文献(1)

[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.

施引文献

资源附件(0)

访问统计