极小强连通块的平均连通度

冯丽华; 田应智

doi:10.13568/j.cnki.651094.651316.2022.03.07.0004

您当前的位置：

首页 >

文章列表页 >

极小强连通块的平均连通度

数理科学 | 更新时间：2026-01-21

- 极小强连通块的平均连通度
- 极小强连通块的平均连通度
- 新疆大学学报（自然科学版中英文） 2023年40卷第1期页码：36-42
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  国家自然科学基金“点(边)-k-极大r-一致超图的边数研究”（12261086）
- DOI：10.13568/j.cnki.651094.651316.2022.03.07.0004
  中图分类号： O157.5
- 纸质出版：2023
- 稿件说明：
移动端阅览
[1]冯丽华,田应智.极小强连通块的平均连通度[J].新疆大学学报(自然科学版)(中英文),2023,40(01):36-42.
[1]冯丽华,田应智.极小强连通块的平均连通度[J].新疆大学学报(自然科学版)(中英文),2023,40(01):36-42. DOI： 10.13568/j.cnki.651094.651316.2022.03.07.0004.

DOI：10.13568/j.cnki.651094.651316.2022.03.07.0004.

摘要

令D=(V (D)

A(D))是一个n阶有向图.如果有向图D是强连通的并且它的底图没有割点

那么称D是一个强连通块.如果D是一个强连通块

但对于任意的a∈A(D)

都有D-a不是一个强连通块

那么称D是一个极小强连通块.对于任意两个点u

v∈V (D)

κD(u

v)表示从u到v的局部连通度

是D中内部不交的(u

v)-有向路的最大条数. D的平均连通度定义为■.借助度序列和耳朵分解的方法

给出了给定阶数的极小强连通块平均连通度的上界

并且猜测其严格小于3/2.

Abstract

Let D =(V(D)

A(D)) be a digraph of order n. The digraph D is called a strong block if D is strongly connected and its underlying graph has no cut-vertex. D is called a minimally strong block

if D is a strong block

but D-a is not a strong block for every arc a of A(D). For u

v ∈ V(D)

the local connectivity κD(u

v)from u to v is the maximum number of internally disjoint directed(u

v)-paths in D. The average connectivity of D is ■. By using the method of degree sequence and ear decomposition

this paper determine some upper bounds of average connectivity among minimally strong blocks in terms of their orders

and conjecture that it is strictly less than 3/2.

关键词

Keywords

references

CASABLANCA R M, MOL L, OELLERMANN O R. Average connectivity of minimally 2-connected graphs and average edgeconnectivity of minimally 2-edge-connected graphs[J]. Discrete Applied Mathematics, 2021, 289:233-247.

TIAN Y Z, MENG J X. Superconnected and hyperconnected 6-regular transitive graphs[J]. Journal of Xinjiang University(Natural Science Edition), 2008, 25(3):253-262.

TIAN Y Z, MENG J X, CHEN X. On restricted edge-connectivity of half-transitive multigraphs[J]. Journal of Xinjiang University(Natural Science Edition), 2018, 35(1):34-41.

ZHANG S, TIAN Y Z, MENG J X. Arc connectivity of balanced half-transitive digraphs[J]. Journal of Xinjiang University(Natural Science Edition), 2014, 31(1):22-25.

DANKELMANN P, OELLERMANN O R. Bounds on the average connectivity of a graph[J]. Discrete Applied Mathematics, 2003,129(2/3):305-318.

ABAJO E, CASABLANCA R M, DIANEZ A, et al. On average connectivity of the strong product of graphs[J]. Discrete Applied Mathematics, 2013, 161(18):2795-2801.

KIM J, SUIL O. Average connectivity and average edge-connectivity in graphs[J]. Discrete Mathematics, 2013, 313(20):2232-2238.

BONDY J A, MURTY U S R. Graph theory[M]. Berlin:Springer, 2008.

JENSEN J B, GUTIN G. Digraphs theory, algorithms and applications[M]. Berlin:Springer, 2007.

GROTSCHEL M. On minimally strong blocks[J]. Journal of Graph Theory, 1979, 3(3):213-219.

GELLER D P. Minimally strong digraphs[J]. Proceedings of the Edinburgh Mathematical Society, 1970, 17(1):15-22.

HENNING M A, OELLERMANN O R. The average connectivity of a digraph[J]. Discrete Applied Mathematics, 2004, 140(1/2/3):143-153.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据