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

依明江·沙比尔; 尚辉; 孟吉翔

doi:10.13568/j.cnki.651094.2018.04.001

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-01-21

- 关于图的生成连通性的综述（英文）
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 35, Issue 4, Pages: 379-388(2018)
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：10.13568/j.cnki.651094.2018.04.001
  CLC： O157.5
- Published：2018
- 稿件说明：
移动端阅览
[1]依明江·沙比尔,尚辉,孟吉翔.关于图的生成连通性的综述（英文）[J],2018,35(04):379-388.
[1]依明江·沙比尔,尚辉,孟吉翔.关于图的生成连通性的综述（英文）[J],2018,35(04):379-388. DOI： 10.13568/j.cnki.651094.2018.04.001.

DOI：10.13568/j.cnki.651094.2018.04.001.

摘要

图G的生成连通度为最大的正整数k使得G的任意两个顶点之间存在i (1≤i≤k)条内部不交的路

并且这些路的并生成G.文章不仅涵盖了有关图的生成连通度的最新研究进展

还包含了图的生成连通度相关的超生成连通性、生成可系性、超生成可系性等问题的最新结果.除此之外

还讨论了一些值得进一步研究的问题.

Abstract

This is intended as a survey paper covering recent progresses in the filed of spanning connectivity

i.e.

the largest integer k such that a graph G contains i internally disjoint paths between any two distinct vertices of G for 1 ≤ i ≤ k and the union of the i paths spans G. This paper also includes some results on related topics such as super spanning connectivity

spanning laceability

super spanning laceability of graphs and digraphs

as well as some research works in the future.

关键词

Keywords

references

Bondy J,Murty U.Graph Theory with Applications[M].New York:Springer,2008.

Menger K.Zur allgemeinen kurventheorie[J].Fundam Math,1927,10:96-115.

Albert M,Aldred R,Holton D.On 3*-connected graphs[J].Austral J Combin,2001,24:193-208.

Hsu L,Lin C.Graph thoery and interconnection networks[M].New York:CRC Press,2008.

Dirac G.In abstrakten Graphen vorhandene vollstaandige 4-Graphen und ihre Unterteilungen[J].Mathematische Nachrichten,1960,22:61-85.

Lin C,Tan J,Hsu D,et al.On the spanning fan-connectivity of graphs[J].Discrete Appl Math,2009,157:1342-1348.

Dirac G.Some theorems on abstract graphs[J].Proc London Math Soc,1952,2:69-81.

Lin C,Huang H,Hsu L.On the spanning connectivity of graphs[J].Discrete Math,2007,307:285-289.

Ore O.Hamilton-connected graphs[J].J Math Pure Appl,1963,42:21-27.

Ore O.Note on Hamilton circutes[J].Amer Math Month,1965,67:55.

Bondy J,Chavatal V.A method in graph theory[J].Discrete Math,2008,15:111-135.

Lin C,Huang H,Tan J,et al.On spanning connected graphs[J].Discrete Math,2008,308:1330-1333.

Fan G.New sufficient cnditions for cycles in graphs[J].J Combin Theory Ser B,1984,37:221-227.

Berman A,Wojda A.The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graphs[J].J Combin Theory Ser B,1987,42:167-180.

Watkins M.A theorem on Tait colorings with an application to the generalized Petersen graphs[J].J Combin Theory B,1969,6:137-142.

Wang J,Hsu L.On the spanning connectivity of the generalized petersen graphs P(n,3)[J].Discrete Math,2018,341:672-690.

Kao S,Hsu H,Hsu L.Globally bi-3*-connected graphs[J].Discrete Math,2009,309:1931-1946.

Zhou J,Feng Y.Cubic vertex-transitive non-Cayley graphs of order 8p[J].Electron J Combin,2012,19:453-472.

Wang X.All doubel generalized Petersen graps are Hamiltonian[J].Discrete Math,2017,340:3016-3019.

Zhan S.Hamilton connectedness of line graphs[J].Ars Combin,1986,22:89-95.

Huang P,Hsu L.The spanning connectivity of line graphs[J].Appl Math Lett,2011,24:1614-1617.

Karaganis J.On the cube of a graph[J].Canad Math Bull,1968,11:295-296.

Sekanina M.On an order of the set of vertices of a connected graph[J].Publ Fac Sci Univ Brno,1960,412:137-142.

Sabir E,Vumar E.Spanning connectivity of the power of a graph and Hamilton-connected index of a graph[J].Graph Combin,2014,2:69-81.

Harary F,Hayes J,Wu H.A survey of the theory of hypercube graphs[J].Comput Math Appl,1988,15:277-289.

Harary F,Lewinter M.Hypercubes and other recursively defined Hamilton laceable graphs[J].Conger Numer,1987,60:81-84.

Chang C,Lin C,Huang H,et al.The subper laceability of hypercubes[J].Inf Process Lett,2004,92:15-21.

Lin C,Tan J,Hsu D,et al.On the spanning connectivity of and spanning laceability of hypercube-like networks[J].Theoret Comput Sci,2007,381:218-229.

Lin C,Ho T,Tan J,et al.Fault-tolerant Hamiltonian laceability and fault-tolerant conditional hamiltonian for bipartite hypercube-like networks[J].J Int Networks,2009,10:243-251.

Lin C,Teng Y,Tan J,et al.The spanning laceability on the faulty bipartite hypercube-like networks[J].Appl Math Comput,2013,219:8095-8103.

Choudum S,Sunitha V.Augmented cubes[J].Networks,2002,40:71-84.

Lin C,Ho T,Tan J,et al.The super spanning connectivity of augmented cubes[J].Ars combin,2012,104:161-167.

Efe K.A variation on the hypercube with lower diameter[J].IEEE Trans Comput,1991,40:1312-1316.

El-Amawy A,Latifi S.Properties and performance of folded hypercubes[J].IEEE Trans Parallel Distrib Syst,1991,2:31-42.

Hsieh S.Some edge fault-tolerant propertices of the folded hypercubes[J].Networks,2008,51:92-101.

Ma M.The spanning connectivity of folded hypercubes[J].Inf Sci,2010,180:3373-3379.

Tzeng N,Wei S.Enhanced hypercubes[J].IEEE Trans Comput,1991,40:284-294.

Chang C,Lin C,Tan J,et al.The super spanning connectivity and super spanning laceability of enhanced hypercubes[J].J Supercomput,2009,48:66-87.

Chin C,Chen H,Hsu L.Super spanning connectivity of the fully connected cubic networks[J].J Int Networks,2011,11:61-70.

Akers S,Krisnamurthy B.A group theoretic model for symmetric network[J].IEEE Trans Comput,1989,38:555-566.

Lin C,Huang H,Hsu L.The super connectivity of the pancake graphs and star graphs[J].Theoret Comput Sci,2005,339:257-271.

Lin C,Ho T,Tan J,et al.A new isomorphic definition of the crossed cube and its super spanning connectivity[J].J Int Networks,2009,10:149-166.

Meng J,Wang S.Hamiltonian property of two class of Cayley graphs[J].J Xinjiang Univ(Natural Sci Edit),1994,11(2):19-21.

Wang A,Meng J.Hamiltonian cylces in Bi-Cayley graphs of finite Abelian groups[J].J Xinjiang Univ(Natural Sci Edit),2006,23(2):156-158.

Chiang W,Chen R.The(n,k)-star graphs:a generalized star graph[J].Inf Process Lett,1995,56:259-264.

Hsu H,Lin C,Huang H.The spanning connectivity of the(n,k)-star graphs[J].Int J Found Comput,2006,17:415-434.

Day D,Tripathi A.Arrangement graphs:a class of generalized star graph[J].Inf Process Lett,1992,42:235-241.

Teng Y.The spanning connectivity of the arrangement graphs[J].J Parallel Distrib Comput,2016,98:1-7.

Fu J.Hamiltonicity of the WK-recursive networks with and without faulty nodes[J].IEEE Trans Parallel Distrib Syst,2005,16:853-865.

You L,Fan J,Han Y.Super spanning connectivity on WK-recursive networks[J].Theory Comput Sci,2018,713:42-55.

Wu J,Huang K.The balanced hypercubes:a cube-baced system for fault-tolerant applications[J].IEEE Trans Comput,1997,46:484-490.

Zhu X.A hypercube variant with small diameter[J].J Graph Theory,2017,85:651-660.

Selcuk B,Karci A.Connected cubic network graph[J].Engin Sci Techno,2017,20:934-943.

Zhang B,Yang W,Zhang S.On the spanning connectivity of tournaments[J].Discrete Appl Math,2018,239:218-222.

Thomassen C.Hamiltonian-connected tournaments[J].Combin Theory Ser B,1980,28:293-298.

Debrujin N.Some machines defined by directed graphs[J].Theory Comput Sci,1984,32:309-319.

Bermond J.The de brujin and kautz networks:a competitor for the hypercube[J].Hypercube distrib Comput,1989,15:273-279.

Li P,Wu Y.Spanning connectedness and hamiltonian thickness of graphs and interval graphs[J].Discrete Math Theor Comput Sci,2015,16:125-210.

Views

117

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

图的生成宽直径（英文）

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

线团图的性质

Related Author

汪亚蒙

边红

艾尔肯·吾买尔

高随祥

Related Institution

新疆大学数学与系统科学学院,新疆大学数学与系统科学学院新疆乌鲁木齐830046

延安大学数学系,

⁰