图的生成宽直径（英文）

汪亚蒙; 依明江·沙比尔

doi:10.13568/j.cnki.651094.651316.2023.11.21.0001

您当前的位置：

首页 >

文章列表页 >

图的生成宽直径（英文）

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

- 图的生成宽直径（英文）
- 图的生成宽直径（英文）
- 新疆大学学报（自然科学版中英文） 2024年41卷第5期页码：571-578
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  supported by the National Natural Science Foundation of the People's Republic of China “On disjoint path covers of graphs and related problems”(12261085);Natural Science Foundation of Xinjiang Uygur Autonomous Region of China “On spanning wide diameter and spanning cycle ability of interconnection networks”(2021D01C116)
- DOI：10.13568/j.cnki.651094.651316.2023.11.21.0001
  中图分类号： O157.5
- 纸质出版：2024
- 稿件说明：
移动端阅览
[1]汪亚蒙,依明江·沙比尔.图的生成宽直径（英文）[J].新疆大学学报(自然科学版中英文),2024,41(05):571-578+590.
[1]汪亚蒙,依明江·沙比尔.图的生成宽直径（英文）[J].新疆大学学报(自然科学版中英文),2024,41(05):571-578+590. DOI： 10.13568/j.cnki.651094.651316.2023.11.21.0001.

DOI：10.13568/j.cnki.651094.651316.2023.11.21.0001.

摘要

图G中两个顶点u和v之间的一个t-container Ct(u

v)是u和v之间的t-条内部不交路的集合

即Ct(u

v)={P1

···

Pt}.进一步

如果V(P1)∪V(P2)∪···∪V(Pt)=V(G)

那么Ct(u

v)称为生成t-container

记作C tsc(u

v).用l(Ctsc(u

v))=max{l(Pi)|1≤i≤t}表示C tsc(u

v)={P1

···

Pt}的长度.图G是生成t-连通的

如果任意两个顶点u和v之间存在一个生成t-container.设u和v是生成t-连通图G中的两个不同的顶点

Dtsc(u

v)是图G中所有C tsc(u

v)的集合

则u和v之间的生成t-宽距离定义为dtsc(u

v)=min{l(Ctsc(u

v))|Ctsc(u

v)∈Dtsc(u

v)}

图G的生成t-宽直径定义为Dtsc(G)=max{dtsc(u

v)|u

v∈V(G)}.特别的

图G的生成宽直径是D_κsc(G)

其中κ是图G的连通度.得到了一般图的生成宽直径的上下界

并证明了界是最优的.除此之外

确定了Harary图、广义Petersen图等常见图类的生成宽直径的精确值.

Abstract

A t-container Ct(u

v) is a set of t internally disjoint paths between two distinct vertices u and v in a graph G

i.e.

Ct(u

v)={P1

···

Pt}.Moreover

if V(P1)∪V (P2)∪···∪V (Pt)=V (G) then Ct(u

v) is called a spanning t-container

denoted by Ctsc(u

v).The length of Ctsc(u

v)={P1

···

Pt}is l(Ctsc(u

v))=max{l(Pi)|1≤i≤t}.A graph G is spanning t-connected if there exists a spanning t-container between any two distinct vertices u and v in G.Assume that u and v are two distinct vertices in a spanning t-connected graph G.Let Dtsc(u

v) be the collection of all Ctsc(u

v)'s.Define the spanning t-wide distance between u and v in G

dtsc(u

v)=min{l(Ctsc(u

v))|Ctsc(u

v)∈Dtsc(u

v)}

and the spanning t-wide diameter of G

Dtsc(G)=max{dtsc(u

v)|u

v∈V (G)}.In particular

the spanning wide diameter of G is D_κsc(G)

whereκis the connectivity of G.In the paper we provide the upper and lower bounds of the spanning wide diameter of a graph

and show that the bounds are best possible.We also determine the exact values of wide diameters of some well known graphs including Harary graphs and generalized Petersen graphs et al..

关键词

Keywords

references

FAUDREE R J.Some strong variations of connectivity[J].Combinatorics,1993,1:125-144.

FLANDRIN E,LI H.Mengerian properties,hamiltonicity,and claw-free graphs[J].Networks,1994,24(3):177-183.

HSU D F.On container width and length in graphs,groups,and networks[J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,1994,77(4):668-680.

FRANK HSU D,UCZAK T.On the k-diameter of k-regular k-connected graphs[J].Discrete Mathematics,1994,133(1/2/3):291-296.

HSU D F,LYU Y D.A graph-theoretical study of transmission delay and fault tolerance[J].International Journal of Mini&Microcomputers,1994,16:35-42.

MA M J,WEST D B,XU J M.The vulnerability of the diameter of the enhanced hypercubes[J].Theoretical Computer Science,2017,694:60-65.

QI H,ZHU X D.The wide-diameter of Zn,K[J].Discrete Applied Mathematics,2017,219:193-201.

QI H,ZHU X D.The fault-diameter and wide-diameter of twisted hypercubes[J].Discrete Applied Mathematics,2018,235:154-160.

LIN C K,HUANG H M,HSU L H.On the spanning connectivity of graphs[J].Discrete Mathematics,2007,307(2):285-289.

HSU L H,LIN C K.Graph theory and interconnection networks[M].Boca Raton:CRC Press,2008.

LIN C K,HUANG H M,HSU D F,et al.On the spanning w-wide diameter of the star graph[J].Networks,2006,48(4):235-249.

CHANG C H,LIN C K,HUANG H M,et al.The super laceability of the hypercubes[J].Information Processing Letters,2004,92(1):15-21.

ALBERT M,ALDRED R E L,HOLTON D,et al.On 3*-connected graphs[J].The Australasian Journal of Combinatorics,2001,24:193-207.

HARARY F,HAYES J P.Edge fault tolerance in graphs[J].Networks,1993,23(2):135-142.

HARARY F,HAYES J P.Node fault tolerance in graphs[J].Networks,1996,27(1):19-23.

SABIR E,VUMAR E.Spanning connectivity of the power of a graph and Hamilton-connected index of a graph[J].Graphs and Combinatorics,2014,30(6):1551-1563.

KAO S S,HSU H C,HSU L H.Globally bi-3*-connected graphs[J].Discrete Mathematics,2009,309(8):1931-1946.

CHANG C H,SUN C M,HUANG H M,et al.On the equitable k*-laceability of hypercubes[J].Journal of Combinatorial Optimization,2007,14(2):349-364.

KOBEISSI M,MOLLARD M.Disjoint cycles and spanning graphs of hypercubes[J].Discrete Mathematics,2004,288(1/2/3):73-87.

WANG J J,HSU L H.On the spanning connectivity of the generalized Petersen graphs P(n, 3)[J].Discrete Mathematics,2018,341(3):672-690.

EMINJAN S,SHANG H,MENG J X.On the spanning connectivity of graphs:A survey[J].Journal of Xinjiang University(Natural Science Edition),2018,35(4):379-388.

浏览量

下载量

CSCD

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

提交

工具集

关联资源

关于图的生成连通性的综述（英文）

关于3-连通图最长圈的注(英文)

线团图的性质