臺灣博碩士論文加值系統

令F⊆V(G)為圖G頂點的子集合，如果G-F造成不連通而且在G-F裡的每個頂點u∈V(G)-F至少有k個在G-F中的鄰居，我們稱F為G的R^k-vertex-cut。G的R^k-vertex-cut的最少個數為G的R^k-vertex-connectivity，以κ^k (G)來表示。在這篇論文中，我們證明了κ^1 (G_n)在n≥3的三價凱利圖G_n的值為4， κ^2 (G_n)在n≥4的三價凱利圖G_n的值為8。

Let G be a graph. A subset F⊂V(G) is called an R^k-vertex-cut of G if G-F is disconnected and each vertex u∈V(G)-F has at least k good neighbors in G-F. The size of a minimum R^k-vertex-cut of G, denoted by κ^k (G), is the R^k-vertex-connectivity of G. In this thesis, we prove that κ^1 (G_n) is equal to 4 for n≥3, κ^2 (G_n) is equal to 8 for n≥4, where G_n is the trivalent Cayley graphs.

CHINESE ABSTRACT ii
ENGLISH ABSTRACT iii
LIST OF FIGURES v
LIST OF TABLES vi
CHAPTER 1 INTRODUCTION 1
1.1 Research background 1
1.2 Motivation 1
1.3 Organization of the thesis 3
CHAPTER 2 RELATED RESEARCH 4
2.1 Conditional vertex connectivity 4
2.2 The relationship between cyclic vertex connectivity and κ^2 6
CHAPTER 3 PROPERTIES OF TRIVALENT CAYLEY GRAPHS 8
3.1 Trivalent Cayley Graphs 8
3.2 Topological properties of trivalent Cayley graphs 10
3.3 Properties of shortest cycle of trivalent Cayley graphs 13
CHAPTER 4 THE CONDITIONAL VERTEX CONNECTIVITY OF TRIVALENT CAYLEY GRAPHS 14
4.1 Some trivalent Cayley graphs properties 14
4.2 Proof of R^1-vertex-connectivity 16
4.3 Proof of R^2-vertex-connectivity 18
CHAPTER 5 CONCLUSION 27
REFERENCES 28

[1]S. B Akers and B. Krishnamurthy, “A group-theoretic model for symmetric interconnection network,” IEEE Trans. Comput, vol. 38, no. 4, pp. 555-566, Apr 1989.
[2]S. B Akers and B. Krishnamurthy, “The star graph: an attractive alternative to n-cube,” in Proc. International Conference on Parallel Processing, St. Charles. IL, pp. 393-400, January 1987.
[3]L. Bhuyan and D. P. Agrawal, “Generalize hypercube and hyperbus structure for a computer network,” IEEE Trans Comput, vol C-33, no. 4, pp. 323-333, April 1984.
[4]K. Qiu, H. Meijer and S. G. Akl, “Decomposing a star graph into disjoint cycles,” Inform. Process. Lett, vol. 39, no. 3, pp. 125-129, August 1991.
[5]K. Qiu, S. G. Akl and H. Merijer, “On some properties and algorithms for the star and pancake interconnection networks,” J. Parallel Distrib. Comput, vol.22, no. 1, pp. 16-25, July 1994.
[6]B. W. Arden and K. W. Tang, “Representation and routing of Cayley graphs,” IEEE Trans. Commun, vol. 39, no. 11, pp. 1533-1537, November 1991.
[7]I. D. Scherson, “Orthogonal graphs for the construction of interconnection networks,” IEEE Trans. Parallel Distribited Systems, vol. 2, no. 1, pp. 3-19, January 1991.
[8]K. Day and A. Tripathi, “Arrangement graphs: A class of generalized star graphs,” Inform. Process. Lett, vol. 42, no. 5, pp. 235-241, July 1992.
[9]S. Lakshmivarahan, J. S Jwo and S. K. Dhall, “Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey,” Parallel Comput, vol. 19, no. 4, pp. 361-407, April 1993.
[10]C. Chen, D. P. Agrawal and J. R. Burke, “dBCube: A new class of hierarchical multiprocessor interconnection networks with area efficient layout,” IEEE Trans. Parallel Distribited Systems, vol. 4, no.12, pp. 1332-1344, December 1993.
[11]M. R. Samatham and D. K. Pradha, “The De Bruijn multiprocessor network: A versatile parallel processing and sorting network for VLSI,” IEEE Trans, Comput, vol. 38, no.4, pp. 567-581, April 1989.
[12]W. E. Leland and M. H. Solomon, “Dense trivalent graphs for processor interconnection,” IEEE Trans. Comput, vol. C-31, no. 3, pp. 219-222, March 1982.
[13]S. G. Akl, “Trivalent Cayley graphs for interconnection networks,” Inform. Process. Lett, vol. 54, no. 6, pp. 329-335, June 1995.
[14]S. B Akers and B. Krishnamurthy, “Group graphs as interconnection networks,” in Proc. FTCS-14, pp. 422-427, 1984.
[15]D. J. Pritchard and D. A. Nicole, “Cube connected Möbius ladders: An inherently deadlock free fixed degree network,” IEEE Trans. Parallel Distribited Systems, vol. 4, no. 1, pp. 111-117, January 1993.
[16]S. Latifi, M. Hegde, and M. Naraghi-Pour, “Conditional connectivity measures for large multiprocessor systems,” IEEE Trans. Comput, vol. 43, no. 2, pp. 218-222, February 1994.
[17]W. Najjr and J. L. Gaudiot, “Network resilience: A measure of network fault tolerance,” IEEE Trans. Comput, vol. 39, no. 2, pp. 174-181, February 1990.
[18]M. Wan and Z. Zhang, “A kind of conditional vertex connectivity of star graphs,” Applied Mathematics Lett, vol. 22, no. 2, pp. 264-267, February 2009.
[19]W. Yang, H. Li and X. Guo, “A kind of conditional fault tolerance of (n,k)-star graph,” Inform. Process. Lett, vol. 110, no. 22, pp. 1007-1011, October 2010.
[20]A. H. Esfahanian, “Generalized measure of fault tolerance with application to N-cube networks,” IEEE Trans. Comput, vol. 38, no. 11, pp. 1586-1591, November 1989.
[21]Z. Zhang, W. Xiong and W. Yang, “A kind of conditional fault tolerance of alternating group graphs,” Inform. Process. Lett, vol. 110, no. 22, pp. 998-1002, October 2010.
[22]Z. Yu, Q. Liu and Z. Zhang, “Cyclic vertex connectivity of star graph,” Lecture Notes in Comput. Sci, vol. 6508, pp. 212-221, 2010.
[23]J. Y. Ke, “Cyclic vertex connectivity of trivalent cayley graphs,” IEICE Trans. INF. & Syst, Submitted.