Some graph properties of the optimised degree six 3-modified chordal ring network
DOI:
https://doi.org/10.11113/mjfas.v12n4.518Keywords:
Parallel processing, modified chordal rings, asymmetry, Hamiltonicity, Eulerity.Abstract
The interconnection topology of a parallel or distributed network is pivotal in ensuring good system performance. It can be modelled by a graph, where its edges represent the links between processor nodes represented by vertices. One such graph model that has gained attention by researchers since its founding is the chordal ring, based on an undirected circulant graph. This paper discusses the degree six 3-modified chordal ring, CHR6o3, and presents its graph theoretical properties of symmetry and Hamiltonicity. CHR6o3 is shown to be asymmetric, and can be decomposed into similar subgraphs, each consisting of only one type of node in its class if ring links are ignored. These properties aid both the development of a routing scheme and also determining lower bounds for its chromatic number. Conditions for the existence of a Hamiltonian Circuit within CHR6o3 are also discussed. The existence of a Hamiltonian Circuit within a network simplifies parallel processing as the processors can be arranged to work on a task in a linear array. An Eulerian Circuit was shown to exist in CHR6o3. The existence of an Eulerian Circuit plays a role in routing in optical networks.
References
B.W. Arden, H. Lee. Analysis of Chordal Ring Network. IEEE Trans. Computer, C-30(4) (1981) 291–295.
R.F. Browne, R.M. Hodgson. Symmetric Degree-four Chordal Ring Networks. IEE, Computers and Digital Techniques, (1990) 310-318.
A.A. Matroud. Communication in Chordal Ring Networks. Ph.D Thesis. Universiti Putra Malaysia. Malaysia. (2006).
S. Bujnowski, B. Dubalski, A. Zabludowski, J.M. Pedersen, T. Riaz. Analysis of Degree 5 Chordal Rings for Network Topologies. Image Processing & Communications Challenges 3, Advances in Intelligent Systems and Computing, 102 (2011) 445-457.
R.N.F Azura, M. Othman, M.H. Selamat, Y.H. Peng. Modified Degree Six Chordal Rings Network Topology. Simposium Kebangsaan Sains Matematik ke-16. (2008) 515-522.
S. Bujnowski, B. Dubalski, A. Zabludowski, D. Ledziński, T. Marciniak, J.M. Pedersen. Comparison of Modified Degree 6 Chordal Rings. Image Processing & Communications Challenges 2, Advances in Intelligent Systems and Computing, 84 (2010) 435-445.
N. Irwan, R.N. Farah, A.Z.M. Sofi. Network Properties for Classes of Chordal Ring Degree Three Topology. International Conference on Intelligent Network and Computing. (2010) 16-20.
B. Dubalski, S. Bujnowski, D. Ledziński, A. Zabłudowski,P. Kiedrowski. Analysis of Modified Fifth Degree Chordal Rings. New Frontiers in Graph Theory. China: InTech. (2012) 43–88.
D. Ledziński, S. Bujnowski, T. Marciniak, J.M. Pedersen, J.G. Lopez. Network Structures Constructed on Basis of Chordal Rings 4th Degree. Image Processing and Communications Challenges 5, Advances in Intelligent Systems and Computing, 233 (2014) 281-299.
L. Barrière. Symmetry Properties of Chordal Rings of Degree 3. Discrete Applied Mathematics, 129 (2003) 211-232.
R.N.F. Azura, M. Othman, Y.H. Peng, M.H. Selamat. On Properties of Modified Degree Six Chordal Rings Network. Malaysian Journal of Mathematical Sciences, 4(2) (2010) 147-157.
L. Narayanan, J. Opatrny. Compact routing on chordal rings of degree four. Algorithmica, 23 (1999) 72-96.
R.N. Farah, M. Othman, M.H. Selamat. An Optimum Free-Table Routing Algorithms of Modified and Traditional Chordal Ring Networks of Degree Four. Journal of Materials Science and Engineering, 4(10) (2012) 78-89.
R.N. Farah, M. Othman. Broadcasting Communication in High Degree Modified Chordal Ring Networks. Applied Mathematics & Information Sciences, 8(1) (2014) 229-233.
B. Parhami. Chordal Rings Based on Symmetric Odd-Radix Number Systems. The 2005 International Conference on Communications in Computing, (2005) 196-199.
R. Kuntal. Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explainations. Journal of Computing and Information Technology 15(1) (2007) 85-92.
L. Narayanan, J. Opatrny, D. Sotteau. All-To-All Optical Routing in Chordal Rings of Degree 4. Algorithmica, 31 (2001) 155-178.
