点传递二部有向图的极大连通性

陈来焕; 张曙亮; 李宁

doi:10.13568/j.cnki.651094.651316.2023.10.06.0002

您当前的位置：

首页 >

文章列表页 >

点传递二部有向图的极大连通性

更新时间：2026-01-21

- 点传递二部有向图的极大连通性
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 41, Issue 2, Pages: 206-208(2024)
- 作者机构：
  
  河南财经政法大学数学与信息科学学院
- 作者简介：
- 基金信息：
- DOI：10.13568/j.cnki.651094.651316.2023.10.06.0002
  CLC： O157.5
- Published：2024
- 稿件说明：
移动端阅览
[1]陈来焕,张曙亮,李宁.点传递二部有向图的极大连通性[J].新疆大学学报(自然科学版)(中英文),2024,41(02):206-208.
[1]陈来焕,张曙亮,李宁.点传递二部有向图的极大连通性[J].新疆大学学报(自然科学版)(中英文),2024,41(02):206-208. DOI： 10.13568/j.cnki.651094.651316.2023.10.06.0002.

DOI：10.13568/j.cnki.651094.651316.2023.10.06.0002.

摘要

有向图X的连通度κ(X)是删除一些点使得剩余的图不再强连通的最小点数.若有向图X的连通度恰好达到最小度

则有向图X是极大连通的.证明了强连通点传递二部有向图是极大连通的

并得出Bi-Cayley有向图也是极大连通的.

Abstract

The connectivity κ(X) of a digraph X is the minimum cardinality of vertices the deletion of which makes the remaining digraph no longer strongly connected. If the connectivity of a digraph X is equal to the minimum degree

then X is said to be maximally vertex-connected. It is proved that a strongly connected vertex-transitive bipartite digraph is maximally vertex-connected

and the Bi-Cayley digraph is also maximally vertex-connected.

关键词

Keywords

references

MADER W.Minimale n-fach kantenzusammenha¨ngende Graphen[J].Mathematische Annalen,1971,191(1):21-28.

TINDELL R.Connectivity of Cayley digraphs[M]//DU D Z,HSU D F.Combinatorial Network Theory.Boston,MA:Springer,1996:41-64.

SHAN E F,ZHAO J,KANG L Y.Maximally connected p-partite uniform hypergraphs[J].Discrete Applied Mathematics,2019,264:188-195.

HARARY F.The maximum connectivity of a graph[J].Proceedings of the National Academy of Sciences of the United States of America,1962,48(7):1142-1146.

FABREGA J,FIOL M A.Maximally connected digraphs[J].Journal of Graph Theory,1989,13(6):657-668.

HELLWIG A,VOLKMANN L.Maximally edge-connected and vertex-connected graphs and digraphs:A survey[J].Discrete Mathematics,2008,308(15):3265-3296.

LI Y K,XIE T,QIN X X.The g-good-neighbor connectivity of some Cartesian product graphs[J].Open Journal of Discrete Mathematics,2023,13(1):27-37.

YANG Y Y,ZHANG M Z,MENG J X,et al.The a-average degree edge-connectivity of bijective connection networks[J].The Computer Journal,2023,66(9):2118-2122.

CHEN L H,LIU F X,MENG J X.The connectivity of hypergraphs[J].Journal of Xinjiang University(Natural Science Edition),2017,34(1):1-6.

BONDY J A,MURTY U S R.Graph theory with applications[M].New York:Springer,2008.

WATKINS M E.Connectivity of transitive graphs[J].Journal of Combinatorial Theory,1970,8(1):23-29.

HAMIDOUNE Y O.On small subset product in a group structure theory of set-addition[J].Asterisque,1999,258:281-308.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

有向循环图的连通度

广义Mycielskian图的连通度(英文)

s-点连通图的路可扩性(英文)

小度数点传递图的连通度(英文)

无限图的笛卡尔积的哈密顿性和连通性

Related Author

刘新

艾尔肯·吾买尔

曹香兰

孟吉翔

薄祥智

陈靓

刘岩

孟吉翔

Related Institution

新疆大学数学系,

新疆大学数学与系统科学学院

新疆大学数学系

新疆大学数学系 ,新疆大学数学系

青海民族学院,

⁰