https://hal.univ-antilles.fr/hal-02350149Culus, Jean-FrançoisJean-FrançoisCulusMEMIAD - Management, économie, modélisation, informatique et aide à la décision - UA - Université des AntillesDemange, MarcMarcDemangeESSEC Business School - Essec Business SchoolMarinescu-Ghemeci, RuxandraRuxandraMarinescu-GhemeciUniBuc - University of BucharestTanasescu, CeraselaCeraselaTanasescuESSEC Business School - Essec Business SchoolCEREGMIA - Centre de Recherche en Economie, Gestion, Modélisation et Informatique Appliquée - UAG - Université des Antilles et de la GuyaneAbout some robustness and complexity properties of G-graphs networksHAL CCSD2015Graphs and groupsG-graphsOrbit graphsOptimal connectivityVertex and edge-transitivityRobustnessNetworkHamming graphsClique graphs[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC][INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM][MATH.MATH-AC] Mathematics [math]/Commutative Algebra [math.AC][MATH.MATH-GR] Mathematics [math]/Group Theory [math.GR]CULUS, Jean-François2019-11-05 23:31:322022-01-21 03:30:342019-11-06 16:12:08enJournal articleshttps://hal.univ-antilles.fr/hal-02350149/document10.1016/j.dam.2014.11.003application/pdf1Given a finite group and a set S ⊂ G, we consider the different cosets of each cyclic group <s> with s ∈ S. Then the G-graph Φ (G,S) associated with G and S can be defined as the intersection graph of all these cosets. These graphs were introduced in Bretto and Faisant (2005) as an alternative to Cayley graphs: they still have strong regular properties but a more flexible structure. We investigate here some of their robustness properties (connectivity and vertex/edge-transitivity) recognized as important issues in the domain of network design. In particular, we exhibit some cases where G-graphs are optimally connected, i.e. their edge and vertex-connectivity are both equal to the minimum degree. Our main result concerns the case of a G-graph associated with an abelian group and its canonical base S, which is shown to be optimally connected. We also provide a combinatorial characterization for this class as clique graphs of Cartesian products of complete graphs and we show that it can be recognized in polynomial time. These results motivate future researches in two main directions: revealing new classes of optimally connected G-graphs and investigating the complexity of their recognition.