赵雪冰, 张昭. 线图的邻域连通度(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2009, 26(4): 379-382.DOI：
线图的邻域连通度(英文)
摘要
研究了图G的边邻域连通度λNB(G)和它的线图L(G)的点邻域连通度κNB(L(G))之间的关系
证明了λNB(G)≤κNB(G).提出了一个新的概念:限制性边邻域连通度λNBr(G)
证明了κNB(L(G))≤λNBr(G).最后
研究了上述两个不等式成为等式的充分条件.
Abstract
In this paper
we study the relationship between the edge neighbor connectivityλNB of agraph G and the(vertex) neighbor connectivityκNB of its line graph L(G)
and prove thatλNB(G)≤κNB(L(G)).We also propose a new concept of restricted edge neighbor connectivityλNB~τ(G)
and provethatκNB(L(G))≤λNB~τ(G).Then we study the problem of when the equalities hold.
关键词
Keywords
references
Gunther G,Hartnell B.On minimizing the effects of betrayals in a resistance movement[C].In:Proceedings of the Eighth Manitoba Conference on Numerical Mathematics and Computing,Winnipeg,Manitoba,Canada,1978,285-306.
Gunther G.Neighbor-connectivity in regular graphs[J].Discr Appl Math,1985,11:233-243.
Gunther G.On the existence of neighbor-connected graphs[J].Congr Numer,1986,54:105-110.
Gunther G,Hartnell B,Nowakovwski R.Neighbor-connected graphs and projective planes[J].Networks,1987,17:241-247.
Gunther G,Hartnell B.On m-connected and k-neighbour-connected graphs[C].In:Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs,Western Michigan University,Kalamazoo,MI,1991, 585-596.
Doty L L,Goldstone R J,Suffel C L.Cayley graphs with neighbor connecitivity one[J].SIAM J Discr Math,1996,9: 625-642.
Doty L L.A new bound for neighbor-connectivity of abelian Cayley graphs[J].Discr Math,2006,306:1301-1316.
Cozzens M B,Wu S Y.Extreme values of the edge-neighbor-connectivity[J].Ars Combin,1995,39:199-210.
Bondy J A,Murty U S R.Graph Theory with Applications[M].London:Macmillan Press,1976.
Xu J M.Topological Structure and Analysis of Interconnection Networks[M].Dordrecht/Boston/London,Kluwer Academic Publisher,2001.
京公网安备11010802024621