Journal of the Iranian Mathematical Society

Journal of the Iranian Mathematical Society

A survey on $G$-graph of group

Document Type : Research Article

Authors
Department of‎ ‎Mathematics, ‎University‎ ‎of Kashan‎, ‎87317-53153, Kashan‎, ‎Iran.
Abstract
In this survey the structure of one of the powerful group presentations, introduced by Alain Bretto is studied which is called $G$-graph. This survey contains some sections of properties, examples, characterization and groups automorphism of $G$-graphs. There are also some well-known graphs that have the structure of $G$-graphs. Moreover, in this survey we compare $G$-graph with the Cayley graph especially to examine the Hamiltonian property of such graphs for a given group. Furthermore by using the construction of a hypergraph, the spectra of the $G$-graph is reported. Finally, in the last section, the structure of the $G$-graph is considered as a network and connectivity property is studied.
Keywords
Subjects

[1] A. Abdollahi and E. Vatandoost, Which Cayley graphs are integral?, Electron. J. Combin. 16 (2009), no. 1, 1–17.
[2] A. R. Ashrafi, A. Bretto and F. Gholaminezhad, The automorphism groups of the involution G-graph and Cayley graph, Southeast Asian Bull. Math. 43 (2019), no. 6, 775–789.
[3] M. Badaoui, G-Graphs and Expander Graphs (G-Graphs et les Graphs D’expansion), PhD thesis, Normandy University, France, 2018.
[4] M. Badaoui, A. Bretto and B. Mourad, On a relationship between Cayley graphs and G-graphs with some applications, Linear Algebra Appl. 582 (2019) 37–57.
[5] M. Badaoui, A. Bretto, D. Ellison and B. Mourad, On constructing expander families of G-graphs, Ars Math. Contemp. 15 (2018), no. 2, 425–440.
[6] C. Bates, D. Bundy, S. Hart and P. Rowley, Commuting involution graphs for sporadic simple groups, J. Algebra 316 (2007), no. 2, 849–868.
[7] R. B. Bapat, Graphs and Matrices, Universitext, Springer, London, 2014.
[8] N. Biggs, Construction for cubic graphs with large girth, Electron. J. Combin. 5 (1998).
[9] A. Bondy and U. Murty, Graph Theory, 1st edition, Graduate Texts in Mathematics, vol. 244, Springer-Verlag, London, 2008.
[10] A. Bretto, Hypergraph Theory: An Introduction, vol. 244, 1st edition, Springer International Publishing, New York, 2013.
[11] A. Bretto and A. Faisant, Another way for associating a graph to a group, Math. Slovaca 55 (2005), no. 1, 1–8.
[12] A. Bretto, A. Faisant, Cayley graphs and G-graphs: some applications, J. Symbolic Comput. 46 (2011), no. 12, 1403–1412.
[13] A. Bretto, A. Faisant and L. Gillibert, New graphs related to (p,6) and (p,8)-cages, Comput. Math. Appl. 62 (2011), no. 6, 2472–2479.
[14] A. Bretto, L. Gillibert and B. Laget, Symmetric and semisymmetric graphs construction using G-graphs, In: International Symposium on Symbolic and Algebraic Computation, (ISSAC’05), 61–67, ACM, New York, 2005.
[15] A. Bretto, A. Faisant and L. Gillibert, G-graphs: a new representation of groups, J. Symbolic Comput. 42 (2007), no. 5, 549–560.
[16] A. Bretto and L. Gillibert, G-graphs: An efficient tool for constructing symmetric and semisymmetric graphs, Discrete Appl. Math. 156 (2008), no. 14, 2719–2739.
[17] A. Bretto, A. Faisant, C. Jaulin and J. Tomanová, Characterization of simple orbit graphs, Acta Math. Univ. Comenian. (N.S.) 79 (2010), no. 2, 175–180.
[18] P. J. Cameron, Topics in Algebraic Graph Theory, Cambridge Univ. Press, 2004, 137–155.
[19] P. H. Zieschang, Cayley graphs of finite groups, J. Algebra 118 (1988), no. 2, 447–454
[20] A. Cayley, The theory of groups: graphical representations, Amer. J. Math. 1 (1878), no. 2, 174–176.
[21] A. Cayley, On the theory of groups, Amer. J. Math. 11 (1889), no. 2, 139–157.
[22] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker and R. A. Wilson, Atlas of Finite Groups, Oxford University Press (Clarendon), Oxford, 1985.
[23] J. F. Culus, M. Demange, R. Marinescu-Ghemeci and C. Tanasescu, About some robustness and complexity properties of G-graphs networks, Discrete Appl. Math. 182 (2015) 34–45.
[24] M. R. Darafsheh and N. S. Poursalavati, On the existence of the orthogonal basis of the symmetry classes of tensors associated with certain groups SUT J. Math. 37 (2001), no. 1, 1–17.
[25] M. R. Darafsheh and M. Abdollahi, Normal edge transitive Cayley graphs on certain groups of orders 4n and 8n, Quasigroups Related Systems 24 (2016), no. 1, 17–23.
[26] M. R. Darafsheh and S. Madady Moghadam, On G-graphs of certain finite groups, Involve 11 (2018), no. 3, 463–476.
[27] D. Ellison, R. Marinescu–Ghemeci and C. Tanasescu, Ggraphs characterisation and incidence graphs, arXiv:1405.3102 (2014).
[28] The GAP Team, GAP, Groups, Algorithms and Programming, Lehrstuhl De fur Mathematik, RWTH, Aachen, 1992.
[29] F. Gholaminezhad, Structures and Topological Indices of Commuting Involution Graphs, Electronic Notes in Discrete Mathematics, 45 (2014) 187–194.
[30] C. Godsil and G. Gordon, Algebraic Graph Theory, in: Graduate Texts in Mathematics, Vol. 207, Springer.
[31] D. Gorenstein, Finite Simple Groups: An Introduction to Their Classification, Springer Science and Business Media, 2013.
[32] T. W. Hungerford, Graduate Text in Mathematics, Algebra, ISBN: 3-540-90518-9, 2000.
[33] H. R. Ho, Hamiltonicity of the graph G(n, k) of the Johnson scheme, Jurnal Informatika 3 (2007), no. 1, 41–47.
[34] D. H. Holton and J. Sheehan, The Petresen Graph, Australian Math. Society lecture, Cambridge Uni. Press, 1993.
[35] L. C. Kavi, A Study of the Structural Properties of Finite G-Graphs and Their Characterisation, The University of Ghana, 2016.
[36] L. Lovász, Problem 11, in: Combinatorial Structures and their Applications, University of Calgary, Calgary, Alberta, Canada, Gordon and Breach, New York, 1970.
[37] A. Mahmiani, Normal Cayley graphs of certain groups which are locally primitive, Facta Univ. Ser. Math. Inform. 31 (2016), no. 1, 73–78.
[38] I. Pak and R. Radoičić, Hamiltonian paths in Cayley graphs, J. Disc. Math. 309 (2009), no. 17, 5501–5508.
[39] P. Turán, On an extremal problem in graph theory, Matematiko Fizicki Lapok 48 (1941) 436–452.
[40] M. Yaghoobian, On Cayley Graphs of Certain Groups, PhD thesis, University of Tehran, 2015.
[41] P. Wong, Cages a survey, J. Graph Theory 6 (1982), no. 1, 1–22.