About some robustness and complexity properties of G-graphs networks

Culus, J, Demange, M, Marinescu-Ghemeci, R and Tanasescu, C 2015, 'About some robustness and complexity properties of G-graphs networks', Discrete Applied Mathematics, vol. 182, pp. 34-45.

Document type: Journal Article
Collection: Journal Articles

Attached Files
Name Description MIMEType Size
n2006049684.pdf Accepted Manuscript application/pdf 445.63KB
Title About some robustness and complexity properties of G-graphs networks
Author(s) Culus, J
Demange, M
Marinescu-Ghemeci, R
Tanasescu, C
Year 2015
Journal name Discrete Applied Mathematics
Volume number 182
Start page 34
End page 45
Total pages 12
Publisher Elsevier BV
Abstract Given a finite group G 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
Subject Operations Research
Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
Analysis of Algorithms and Complexity
Keyword(s) Graphs and groups
Orbit graphs
Optimal connectivity
Vertex and edge-transitivity
Hamming graphs
Clique graph
DOI - identifier 10.1016/j.dam.2014.11.003
Copyright notice © 2014 Elsevier B.V. All rights reserved.
ISSN 0166-218X
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 0 times in Scopus Article
Altmetric details:
Access Statistics: 277 Abstract Views, 42 File Downloads  -  Detailed Statistics
Created: Wed, 04 Feb 2015, 13:27:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us