Geometric representations of distinct Hamiltonian circuits in complete graph decomposition

Geometric representations of distinct Hamiltonian circuits in complete graph decomposition

Visualization of geometric representations of distinct Hamiltonian circuits in complete graphs is needed to avoid structures resemblance in real application. However, there are only a few studies that consider graph visualization, whereas most researchers focus on computation time. Thus, this study...

Full description

Saved in:
Bibliographic Details
Main Author: Maizon, Mohd Darus
Format: Thesis
Language:eng
eng
Published: 2015
Subjects:
QA Mathematics
Online Access:https://etd.uum.edu.my/5322/1/s808768.pdf
https://etd.uum.edu.my/5322/2/s808768_abstract.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-uum-etd.5322
record_format uketd_dc
institution Universiti Utara Malaysia
collection UUM ETD
language eng
eng
advisor Ibrahim, Haslinda
Karim, Sharmila
topic QA Mathematics
spellingShingle QA Mathematics
Maizon, Mohd Darus
Geometric representations of distinct Hamiltonian circuits in complete graph decomposition
description Visualization of geometric representations of distinct Hamiltonian circuits in complete graphs is needed to avoid structures resemblance in real application. However, there are only a few studies that consider graph visualization, whereas most researchers focus on computation time. Thus, this study aims to construct a novel picturing method called Half Butterfly Method (HBM) to address the aforementioned scenario. Towards developing HBM, the concept of Wing Strategy is introduced to create directions from one vertex to another vertex. Then, these directions are used to map distinct vertices. In order to obtain the distinct Hamiltonian circuits, the concept of matrix transpose is used to capture the mirror image of that circuit. Several new theorems and lemmas are proved in the decomposition of complete graphs into distinct Hamiltonian circuits. Furthermore, the result of HBM is applied to list.
format Thesis
qualification_name masters
qualification_level Master's degree
author Maizon, Mohd Darus
author_facet Maizon, Mohd Darus
author_sort Maizon, Mohd Darus
title Geometric representations of distinct Hamiltonian circuits in complete graph decomposition
title_short Geometric representations of distinct Hamiltonian circuits in complete graph decomposition
title_full Geometric representations of distinct Hamiltonian circuits in complete graph decomposition
title_fullStr Geometric representations of distinct Hamiltonian circuits in complete graph decomposition
title_full_unstemmed Geometric representations of distinct Hamiltonian circuits in complete graph decomposition
title_sort geometric representations of distinct hamiltonian circuits in complete graph decomposition
granting_institution Universiti Utara Malaysia
granting_department Awang Had Salleh Graduate School of Arts & Sciences
publishDate 2015
url https://etd.uum.edu.my/5322/1/s808768.pdf
https://etd.uum.edu.my/5322/2/s808768_abstract.pdf
_version_ 1747827908203773952
spelling my-uum-etd.53222021-04-04T07:32:55Z Geometric representations of distinct Hamiltonian circuits in complete graph decomposition 2015 Maizon, Mohd Darus Ibrahim, Haslinda Karim, Sharmila Awang Had Salleh Graduate School of Arts & Sciences Awang Had Salleh Graduate School of Arts & Sciences QA Mathematics Visualization of geometric representations of distinct Hamiltonian circuits in complete graphs is needed to avoid structures resemblance in real application. However, there are only a few studies that consider graph visualization, whereas most researchers focus on computation time. Thus, this study aims to construct a novel picturing method called Half Butterfly Method (HBM) to address the aforementioned scenario. Towards developing HBM, the concept of Wing Strategy is introduced to create directions from one vertex to another vertex. Then, these directions are used to map distinct vertices. In order to obtain the distinct Hamiltonian circuits, the concept of matrix transpose is used to capture the mirror image of that circuit. Several new theorems and lemmas are proved in the decomposition of complete graphs into distinct Hamiltonian circuits. Furthermore, the result of HBM is applied to list. 2015 Thesis https://etd.uum.edu.my/5322/ https://etd.uum.edu.my/5322/1/s808768.pdf text eng public https://etd.uum.edu.my/5322/2/s808768_abstract.pdf text eng public http://sierra.uum.edu.my/record=b1272239~S1 masters masters Universiti Utara Malaysia Adams, P., Bryant, D. E., Forbes, A. D., & Griggs, T. S. (2012). Decomposing the complete graph into dodecahedra. Journal of Statistical Planning and Inference, 142(5), 1040–1046. Akbari, S., & Herman, A. (2007). Commuting decompositions of complete graphs. Journal of Combinatorial Designs, 15, 133-142. Alon, N., & Erdos, P. (1989). Disjoint edges in geometric graphs. Discrete and Computational Geometry, 4(1), 287-290. Alon, N., & Perles, M. (1986). On the intersection of edges of a geometric graph by straight line. Discrete Mathematics, 60, 75-90. Anitha, R., & Lekshmi, R. S. (2008). N-Sun decomposition of complete, complete bipartite and some harary graphs. International Journal of Mathematics Sciences, 2(1), 33-38. Avital, S., & Hanani, H. (1966). Graphs. Gilyonot Lematematika, 3, 2-8 (in Hebrew). Babar, G. M., Khiyal, S. H., & Saeed, A. (2006). Finding Hamilton circuit in a graph. Paper presented at the International Conference on Scientific Computing, CSC 2006, Las Vegas, Nevada, USA. Botton, Q., Fortz, B., Gouveia, L., & Poss, M. (2013). Benders decomposition for the hop-constrained survivable network design problem. INFORMS Journal on Computing, 25(1), 13-42. Brualdi, R. A., & Schroeder, M. W. (2011). Symmetric Hamilton cycle decompositions of complete graphs minus a 1-factor. Journal of Combinatorial Designs, 19(1), 1-15. Chalaturnyk, A. (2008). A fast algorithm for finding Hamilton cycles. (Unpublished Masters Dissertation), University of Manitoba, Canada. Choi, D., Lee, O., & Chung, I. (2008). A parallel routing algorithm on recursive cube of rings networks employing the Hamiltonian circuit Latin square. Information Sciences, 178(6), 1533-1541. Chung, I. (2000). Construction of a parallel and shortest routing algorithm on recursive circulant networks. Paper presented at the Fourth International Conference on High-Performance Computing in the Asia-Pacific Region, Beijing, China. Cranston, D. W. (2008). Nomadic Decompositions of Bidirected Complete Graphs. Discrete Mathematics, 308(17), 3982-3985. Dharwadker, A. (2004). A new algorithm for finding Hamiltonian circuits. Paper presented at the Proceedings of the Institute of Mathematics on December 2004, University of Alaska, Fairbanks. Dong, R. & Kresman, R. (2010). Notes of privacy-preserving distributed mining and Hamiltonian cycles. Paper presented at the Fifth International Conference on Software and Data Technologies, Athens, Greece. Froncek, D., Kovar, P., & Kubesa, M. (2010). Decompositions of complete graphs into blown-up cycles Cm[2]. Discrete Mathematics, 310(5), 1003-1015. Fu, H. L., Hwang, F. K., Jimbo, M., Mutoh, Y., & Shiue, C. L. (2004). Decomposing complete graphs into Kr x Kc's. Journal of Statistical Planning and Inference, 119, 225-236. Gopal, A. P., Kothapalli, K., Venkaiah, V. C., & Subramaniam, C. R. (2007, April 2). Various one-factorizations of complete graphs. 2007 Technical Report at International Institute of Information Technology, Hyderabad, India. Retrieved from http://people.csail.mit.edu/ prasant/factorizations.pdf Granville, A., Moisiadis, A., & Rees, R. (1989). On complementary decompositions of complete graph. Graphs and Combinatorics, 5(1), 57-61. Grebinski, V. (1998). Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping. Discrete Applied Mathematics, 88, 147-165. Gyarfas, A., Ruszinko, M., Sarkozy, G. N., & Szemeredi, E. (2011). Partitioning 3-coloured complete graphs into three monochromatic cycles. The Electronic Journal of Combinatorics, 18, P53. Herman, I., Melancon, G., & Marshall, M. S. (2000). Graph visualization and navigation in information visualization. IEEE Transactions on Visualization and Computer Graphics: A Survey, 6(1), 24-43. Hurley, E., & Oldford, R. W. (2008). Eulerian tour algorithms for data visualization and the PairViz package. Computational Statistics, 26(4), 613-633. Hwang, S. C., & Chen, G. H. (2000). Fault-free Hamiltonian cycles in faulty butterfly graphs. Paper presented at the Seventh International Conference on Parallel and Distributed Systems, Iwate, Japan. Ibrahim, H., Omar, Z., & Rohni, A. M. (2010). New algorithm for listing all permutations. Modern Applied Science, 4(2), 89-94. Jeron, T., & Jard, C. (1995). 3D layout of reachability graphs of communicating processes. Paper presented at the DIMACS International Workshop on Graph Drawing, Princeton, NJ, USA. Kante, M. M. (2008). Graph Structurings: Some Algorithmic Applications. (Unpublished Doctoral Dissertation), University of Bordeaux I, Talence, France. Kaski, P., & Ostergard, P. R. J. (2009). There are 1, 132, 835, 421, 602, 062, 347 nonisomorphic one-factorizations of K14. Journal of Combinatorial Designs, 17(2), 147-159. Kumar, C. S. (2003). On P4-decomposition of graphs. Taiwanese Journal of Mathematics, 7(4), 657-664. Lovasz, L. (2009). Geometric Representations of Graphs. (Unpublished Doctoral Dissertation), Eö tvö s Loránd University, Budapest, Hungary. Marcialis, G. L., Roli, F., & Serrau, A. (2007). Graph-based and structural methods for fingerprint classification. Applied Graph Theory in Computer Vision and Pattern Recognition, 52, 205-226. Munzner, T. (2000). Interactive Visualization of Large Graphs and Networks. (Unpublished Doctoral Dissertation), Stanford University, Carlifornia, USA. Raney, R. K., Cahill, J. T. S., Patterson, G. W., & Bussey, D. B. J. (2012). The m-chi decomposition of hybrid dual-polarimetric radar data with application to lunar craters. Journal of Geophysical Research, 117(21). doi: 10.1029/2011JE003986 Rao, M. (2006). Décompositions de Graphes et Algorithmes Efficaces. (Unpublished Doctoral Dissertation), Université Paul Verlaine, Metz, France. Rapanotti, L., Hall, J.G., Jackson, M., & Nuseibeh, B. (2004). Architecture-driven problem decomposition. Paper presented at the 12th International Conference on Requirements Engineering, Kyoto, Japan. Riaz, K., & Khiyal, M. S. H. (2006). Finding Hamiltonian cycle in polynomial time. Information Technology Journal, 5(5), 851-859. Rosen, K. H. (2013). Discrete Mathematics and Its Applications (3rd ed.). New York, USA: Mc Graw Hill. Samee, M. A., & Rahman, M. S. (2007). Visualization of complete graphs, trees and series-parallel graphs for practical applications. Paper presented at the International Conference on Information and Communication Technology, Dhaka, Bangladesh. Shai, O., & Preiss, K. (1999). Graph theory representations of engineering systems and their embedded knowledge. Artificial Intelligence in Engineering, 13(3), 273-285. Shi, H. Z. & Niu, P. F. (2009). Hamiltonian decomposition of some interconnection networks. Combinatorial Optimization and Applications, 5573, 231-237. Shirinivas, S. G., Vetrivel, S., & Elango, N. M. (2010). Applications of graph theory in computer science: An overview. International Journal of Engineering Science and Technology, 2(9), 4610-4621. Simonetto, P. (2011). Visualisation of Overlapping Sets and Clusters with Euler Diagrams. (Unpublished Doctoral Dissertation), Université Bordeaux 1, Talence, France. Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley. Studer, C., Blosch, P., Friedli, P., & Burg, A. (2007). Matrix decomposition architecture for MIMO systems: design and implementation trade-offs. Paper presented at the Conference Record of the 41st Asilomar Conference, Pacific Grove, CA, USA. Toth, G., & Valtr, P. (1999). Geometric graphs with few disjoint edges. Discrete Computational Geometry, 22, 633-642. West, D. B. (2001). Introduction to Graph Theory (2nd ed.). USA: Prentice Hall. Wilson, R. J. (1988). A brief history of Hamiltonian graphs. Annals of Discrete Mathematics, 41, 487-496. Yuan, L. D., & Kang, Q. D. (2012). Decompostion of λKv into five graphs with six vertices and eight edges. Acta Mathematicae Applicatae Sinica, English Series, 28(4), 823-832.

Similar Items