On constructing expander families of G-graphs

被引：3

作者：

Badaoui, Mohamad ^{[1
,2
]}

Bretto, Alain ^{[1
]}

Ellison, David ^{[3
]}

Mourad, Bassam ^{[4
]}

机构：

[1] Normandie Univ Caen, CNRS, GREYC, UMR 6072, Campus 2,Bd Marechal Juin BP 5186, F-14032 Caen, France

[2] Lebanese Univ, Lab Math, EDST, Rafic Hariri Univ Campus,Hadath POB 5, Beirut, Lebanon

[3] RMIT Univ, 124 Little Trobe St, Melbourne, Vic 3000, Australia

[4] Lebanese Univ, Dept Math, Fac Sci, Beirut, Lebanon

来源：

ARS MATHEMATICA CONTEMPORANEA | 2018年 / 15卷 / 02期

关键词：

Cayley graph; diameter of a graph; abelian group; G-graph; expander family;

D O I：

10.26493/1855-3974.1537.97c

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Like Cayley graphs, G-graphs are graphs that are constructed from groups. A method for constructing expander families of G-graphs is presented and is used to construct new expander families of irregular graphs. This technique depends on a relation between some known expander families of Cayley graphs and certain expander families of G-graphs. Several other properties of expander families of G-graphs are presented.

引用

页码：425 / 440

页数：16

共 23 条

[1]

[Anonymous], 1983, 15 ACM STOC, DOI DOI 10.1145/800061.808726

[2]

[Anonymous], 1999, LONDON MATH SOC STUD, DOI DOI 10.1017/CBO9780511626265

[3]

Bondy JA., 2008, Graph Theory, GTM 244, DOI [DOI 10.1007/978-1-84628-970-5, 10.1007/978-1-84628-970-5]

[4]

Bonvicini S, 2017, ARS MATH CONTEMP, V12, P1

[5]

Bretto A., 2005, INT S SYMB ALG COMP, P61, DOI [10.1145/1073884.1073895, DOI 10.1145/1073884.1073895]

[6] G-graphs:: A new representation of groups [J].

Bretto, Alain ;

Faisant, Alain ;

Gillibert, Luc .

JOURNAL OF SYMBOLIC COMPUTATION, 2007, 42 (05) :549-560

[7] Cayley graphs and G-graphs: Some applications [J].

Bretto, Alain ;

Faisant, Alain .

JOURNAL OF SYMBOLIC COMPUTATION, 2011, 46 (12) :1403-1412

[8] New graphs related to (p, 6) and (p, 8)-cages [J].

Bretto, Alain ;

Faisant, Alain ;

Gillibert, Luc .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2011, 62 (06) :2472-2479

[9] STRONG UNIFORM EXPANSION IN SL(2, p) [J].

Breuillard, Emmanuel ;

Gamburd, Alex .

GEOMETRIC AND FUNCTIONAL ANALYSIS, 2010, 20 (05) :1201-1209

[10] About some robustness and complexity properties of G-graphs networks [J].

Culus, Jean-Francois ;

Demange, Marc ;

Marinescu-Ghemeci, Ruxandra ;

Tanasescu, Cerasela .

DISCRETE APPLIED MATHEMATICS, 2015, 182 :34-45

← 1 2 3 →