Bi-super-connected digraphs
-
摘要: 简单有向图(无环与重弧),如果满足每个最小点割都是某个点的出邻点集或入邻点集,则称是超连通的. 在超连通有向图中,如果存在一个最小点割既是某个点的出邻点集又是某个点的入邻点集,则称是双超连通的. 主要研究了线图双超连通性的充要条件; 同时,研究了笛卡尔积与字典积的双超连通性.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.
-
[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.
点击查看大图
计量
- 文章访问数: 769
- HTML全文浏览量: 34
- PDF下载量: 780
- 被引次数: 0