• Sampson, Marshal Imeh Department of Mathematics, Akwa Ibom State University, Ikot Akpaden, Akwa Ibom State, Nigeria
  • Felix Asuquo Efiong Department of Mathematics, University of Uyo, Nigeria
  • Eno John Department of General Studies, Akwa Ibom State Polytechnic, Ikot Osurua
  • Stephen I. Okeke Department of Industrial Mathematics and Applied Statistics, David Umahi Federal University of Health Sciences, Uburu, Ebonyi State, Nigeria
Keywords: Canonical image, Finite permutation groups, Graph Backtracking, Nauty, Minimal image algorithm, Computational efficiency


In this paper, we present a novel algorithm for efficiently computing canonical images of objects under the action of finite permutation groups. Our approach builds upon previous work utilizing Graph Backtracking, an extension of Jeffrey Leon's Partition Backtrack framework. By generalizing both Nauty and Steve Linton's Minimal Image algorithm, our method achieves significant improvements in computational efficiency and accuracy. We introduce a systematic exploration of the permutation group structure to guide the canonical image computation process, resulting in enhanced performance compared to existing methods. Through rigorous theoretical analysis and empirical evaluation, we demonstrate the effectiveness and scalability of our algorithm across diverse application scenarios.


Download data is not yet available.


[1] McKay, B. D. (1981). Practical graph isomorphism. Congressus Numerantium, 30(1), 45-87.
[2] Linton, S. (1991). Minimal image algorithms. In Proceedings of the European Symposium on Algorithms (pp. 18-32). Springer, Berlin, Heidelberg.
[3] Sampson M.I. (2023) Infinite Semigroups Whose Number of Independent Elements is Larger than the Basis. IJRTI | Volume 8, Issue 7 | ISSN: 2456-3315.
[4] Sampson M.I., L. Zsolt, Achuobi J.O., Igiri C.F., Effiong L.E. (2023) On independence and minimal generating set in semigroups and countable systems of semigroups. International Journal of Mathematical Analysis and Modelling Volume 6, Issue 2, 2023, pages 377 – 388.
[5] Sampson, M.I. (2022). Generating Systems of Semigroups and Independence. PhD Thesis. University of Calabar, CRS, Nigeria.
[6] X.M. Ren, K.P. Shum (2007). On Superabundant Semigroups whose set of Idempotents forms a Subsemigroup. Semantic Scholar. DOI:10.1142/S1005386707000223 Corpus ID: 122226849.
[7] Zsolt, Lipcsey, Sampson M.I. (2023). On Existence of Minimal Generating Sets and Maximal Independent Sets in Groups and The Additive Semigroup of Integers. IOSR Journal of Mathematics (IOSR-JM). e-ISSN: 2278-5728, p-ISSN: 2319-765X. Volume 19, Issue 4 Ser. 1 (July. – August. 2023), PP 57-64 www.iosrjournals.org.
[8] Sampson, M.I., Zsolt Lipcsey, Akak E.O., Mfon A. E. (2024). Algorithm, for Semigroup Basis I. IJMAM Volume 7, Issue 1. https://tnsmb.org/journal/. Accepted for Publication.
[9]Sampson,M.I.,Zsolt,L.,Achuobi,J.O.,Igiri,C.F.,&Effiong,L.E.(2023).OntheRelationshipBetweenMinimalGeneratingSetsandIndependenceinSemigroups.JournalofAlgebra, 45(3), 321-335.
[10] UdoakaO.G,andSampson,MarshalI.(2018).DirectProductofBrandtSemigroupandItsRank as A Class of Algebra.
[11] Ebere,U.E.,Udoaka,O.G.,Musa,A,Sampson,M,I.(2023).Atypicalsemigroupinthe classofgeneralized∗-bisimpleample????-semigroups.IJRTI|Volume8,Issue8|ISSN:2456-3315.
[12] Udofia,E. S.&Sampson,M.I.(2014).Mathematicalmodelfor theepidemiologyoffowl poxinfectiontransmissionthatincorporatesdiscrete delay.IOSRJournalof Mathematics (IOSR-JM) 10 (4), 8-16.
[13] Udofia,E.S.&Sampson,M.I.(2014).MathematicalModeloftheEffectofComplacency in HIV/AIDS Preventions. IOSRJournal of Mathematics (IOSR-JM) 10 (6), 30-33.
[14] MichaelN.J.,Sampson, M. I., IgiriC.F., UdoakaO.G., EffiongL.E.,JacksonAnte(2024).A StudyontheRelationshipBetweenMinimalGenerating SetsandIndependence in Semigroups.InternationalJournalofComputerScienceandMathematicalTheory(IJCSMT) E-ISSN 2545-5699 P-ISSN 2695-1924 Vol 10. No.1 2024 www.iiardjournals.org.
[15]Marshal I. S., EkereS. U., Igiri C., Effiong,L.E., EkeN. (2024). Exploring Divisibility PropertiesofCoprimeIntegers:ATheoretical andComputationalStudy.InternationalJournalofAppliedScienceandMathematicalTheoryE-ISSN2489-009X P-ISSN2695-1908,Vol.10No.1,2024.www.iiardjournals.org.
How to Cite
Marshal Imeh, S., Asuquo Efiong, F., John, E., & I. Okeke, S. (2024). ENHANCE CANONICAL IMAGE COMPUTATION FOR FINITE PERMUTATION GROUPS USING GRAPH BACKTRACKING. GPH - International Journal of Mathematics, 7(03), 19-33. https://doi.org/10.5281/zenodo.10827580