Some results on R 2-edge-connectivity of even regular graphs
Tóm tắt
Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an R
2-edge-cut if G-S is disconnected and contains neither an isolated vertex nor a one-degree vertex. The R
2-edge-connectivity of G, denoted by λ
n(G), is the minimum cardinality over all R
2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ
n(G)=g(2k−2) for any 2k-regular connected graph G(≠K
5) that is either edge-transitive or vertex-transitive and g≥5 is given.
Tài liệu tham khảo
Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, Macmillan Press, London, 1976.
Esfahanian, A. H., Generalized measures of fault tolerance with application to N-cube networks, IEEE Trans. Comput., 1989,38:1586–1591.
Latifi, S., Hegde, M., Naraghi-Pour, M., Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput., 1994,43:218–221.
Esfahanian, A. H., Hakimi, S. L., On computing a conditional edge-connectivity of a graph, Information Processing Letters, 1988,27:195–199.
Li, Q. L., Graph theoretical studies on fault-tolerance and reliability of networks (Chinese): [Ph.D. Thesis], University of Science and Technology of China, Hefei, 1997.
Li, Q. and Zhang, Y., Restricted connectivity and restricted fault diameter of some interconnection networks, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 1995,21:267–273.
Watkins, A. E., Connectivity of transitive graphs, J. Combin. Theory, 1970,8:23–29.
Lovasz, L., Combinatorial Problems and Exercises, North-Holland Publishing Company, Amsterdam, New York, Oxford, 1979.