Table I shows the spectrum of
${X}^{3,q}$
for
$q\in \{5,7,11\}$
and Table II that of
${X}^{5,q}$
for
$q\in \{7,11\}$
. Numerical computations of eigenvalues reported in this paper have been computed with Mathlab.
Proposition 1
If the graph
${X}^{p,q}$
is bipartite,
${X}^{p,q}$
and its bipartite complement
$\overline{{X}^{p,q}}$
have perfect matchings.
Proof This is a case of the “Marriage Theorem”; see for example Corollary 1.1.4 in [LovPl–86]. Here is another reason for
${X}^{p,q}$
(bipartite or not): any connected vertextransitive graph of even order has a perfect matching (Section 3.5 in [GodRo–01]); this applies in particular to Cayley graphs of finite groups of even order, such as
$PG{L}_{2}\left(q\right)$
and
$PS{L}_{2}\left(q\right)$
.
$\square $
Proposition 2
Let
$X=(V,E)$
be a finite graph with
$n$
vertices and with eigenvalues
${\lambda}_{0}\ge {\lambda}_{1}\ge ...\ge {\lambda}_{n1}$
. Let
$F$
be a matching of
$X$
[respectively of the complement
$\overline{X}$
] and let
${\mu}_{0}\ge {\mu}_{1}...\ge {\mu}_{n1}$
be the eigenvalues of
$XF$
[respectively
$X+F$
]. Then
${\mu}_{j}{\lambda}_{j}\le 1$
for
$j\in \{0,1,...,n1\}$
.
Proof Outside diagonal entries, the adjacency matrix
${A}_{F}$
of
$(V,F)$
coincides with a matrix of permutation (the permutation being a nonempty product of transpositions with disjoint supports, one transposition for each edge in
$F$
). Thus
$\parallel {A}_{F}\parallel \le 1$
.
Here, the norm of a matrix acting on the Euclidean space
${\mathbb{R}}^{V}$
is the operator norm
$\parallel {A}_{F}\parallel =sup\left\{\parallel Af{\parallel}_{2}f\in {\mathbb{R}}^{V},\parallel f{\parallel}_{2}\le 1\right\}$
, where
$\parallel f{\parallel}_{2}^{2}={\sum}_{v\in V}\leftf\right(v){}^{2}$
.
Thus Proposition 1 follows from the classical CourantFischerWeyl minimax principle, according to which eigenvalues of symmetric operators are norms of appropriate restrictions of these operators. See e.g. Chapter III in [Bhati–97].
$\square $
3 Tables
There are several standard efficient algorithms to find a perfect matching
$F$
in a graph
$X$
; see [LovPl–86] and [West–01], among others. We will not describe here the details of the algorithm we have used. Eigenvalues of
$XF$
can then be computed with Mathlab. The eigenvalues of a graph of the form
${X}^{p,q}F$
depend on the choice of
$F$
. Table III gives for each of three pairs
$(p,q)$
the values of the spectral gaps
$p{\lambda}_{1}({X}^{p,q}F)$
corresponding to four different
$F$
. Table III shows that there are situations (
$p=5,q=7$
) with
${\lambda}_{0}(XF)=k1<{\lambda}_{0}\left(X\right)=k$
and
${\lambda}_{1}(XF)>{\lambda}_{1}\left(X\right)$
.
Table IV shows the full spectrum of
${X}^{3,5}F$
for one specific
$F$
. Tables V to VII show the ten largest eigenvalues of three graphs of the form
${X}^{p,q}+F$
. Observe that the multiplicities in Tables IV to VII are much less than those of the unperturbed graphs.
Table I: spectra of
${X}^{3,q}$

q=5

q=7

q=11

eigenvalues

multiplicities

eigenvalues

multiplicities

eigenvalues

multiplicities

4.0000

1

4.0000

1

3.2361

30

3.0000

12

3.0000

24

3.0000

33

2.0000

28

2.8284

30

2.7321

10

1.0000

4

2.0000

28

2.6180

24

0.0000

30

1.4142

24

2.3723

10

1.0000

4

1.0000

40

2.0468

36

2.0000

28

0.0000

42

2.0000

10

3.0000

12

1.0000

40

1.6180

36

4.0000

1

1.4142

24

1.5616

33



2.0000

28

0.9191

36



2.8284

30

0.7321

30



3.0000

24

0.3820

24



4.0000

1

0.0000

30





0.3820

12





0.6180

36





0.7321

10





1.0000

52





1.2361

30





1.9191

36





2.0000

20





2.5616

33





2.6180

12





2.7321

30





3.0468

36





3.3723

10





4.0000

1


Table II: spectra of
${X}^{5,q}$

q=7

q=11

eigenvalues

multiplicities

eigenvalues

multiplicities

6.0000

1

4.0243

36

4.0000

21

3.7321

30

3.0000

16

3.0000

65

2.8284

42

2.2361

30

2.0000

21

1.7321

10

1.4142

12

1.6180

60

1.0000

48

1.3723

10

0.0000

14

1.2361

12

1.0000

48

0.5616

33

1.4142

12

0.2679

30

2.0000

21

0.1638

36

2.8284

42

0.6180

60

3.0000

16

1.0000

30

4.0000

21

1.7321

10

6.0000

1

1.7818

36



2.2361

30



3.0000

50



3.2361

12



3.4063

36



3.5616

33



4.3723

10



6.0000

1


Table III: spectral gaps for
${X}^{p,q}F$

p=3,q=5

p=3,q=7

p=5,q=7

0.4457

0.2499

0.7910

0.3025

0.1862

0.7732

0.2993

0.1785

0.7367

0.2702

0.0272

0.7152


Table IV: spectrum of
${X}^{3,5}F$

eigenvalues

multiplicities

3.0000

1

2.5543

8

2.5450

4

2.1542

4

2.0000

6

1.8829

8

1.2929

8

1.0000

3

0.8302

4

0.5086

8

0.4394

4

0.0000

4

0.4394

4

0.5086

8

0.8302

4

1.0000

3

1.2929

8

1.8829

8

2.0000

6

2.1542

4

2.5450

4

2.5543

8

3.0000

1


Table V: largest eigenvalues for
${X}^{3,5}+F$

eigenvalues

multiplicities

eigenvalues

multiplicities

eigenvalues

multiplicities

3.2578

1

3.2163

1

3.1707

1

3.3225

1

3.3208

1

3.1998

1

3.3425

1

3.3431

1

3.2214

1

3.4295

1

3.4417

1

3.2418

1

3.4859

1

3.4992

1

3.3046

1

3.5140

1

3.5358

1

3.5525

1

3.5687

1

3.6211

1

3.5653

1

3.5950

1

3.6822

1

3.5935

1

3.6758

1

3.8466

1

3.6547

1

5.0000

1

5.0000

1

5.0000

1


Table VI: largest eigenvalues for
${X}^{3,7}+F$

eigenvalues

multiplicities

eigenvalues

multiplicities

eigenvalues

multiplicities

3.6042

1

3.6199

1

3.6138

1

3.6130

1

3.6478

1

3.6431

1

3.6349

1

3.6594

1

3.6524

1

3.6728

1

3.6826

1

3.6726

1

3.6892

1

3.6996

1

3.6922

1

3.6971

1

3.7203

1

3.7131

1

3.7073

1

3.7468

1

3.7275

1

3.7505

1

3.7548

1

3.7461

1

3.7697

1

3.7752

1

3.7985

1

5.0000

1

5.0000

1

5.0000

1


Table VII: largest eigenvalues for
${X}^{5,7}+F$

eigenvalues

multiplicities

eigenvalues

multiplicities

eigenvalues

multiplicities

4.3702

1

4.3388

1

4.3229

1

4.4015

1

4.3738

1

4.3405

1

4.4271

1

4.4326

1

4.3882

1

4.4625

1

4.4790

1

4.4117

1

4.4888

1

4.5124

1

4.4671

1

4.4971

1

4.5618

1

4.5585

1

4.5819

1

4.5925

1

4.5875

1

4.5976

1

4.6417

1

4.6341

1

4.6512

1

4.6892

1

4.7260

1

7.0000

1

7.0000

1

7.0000

1


References

[Bhati–97
] R. Bhatia, Matrix analysis, Graduate Texts in Mathematics 169, Springer 1997

[Colin–98
] Y. Colin de Verdière, Spectres de graphes, Cours spécialisés 4, Soc. Math. France 1998.

[DaSaV–03
] G. Davidoff, P. Sarnak, and A. Valette, Elementary number theory, group theory, and Ramanujan graphs, London Math. Soc. Student Texts 55, Cambridge Univ. Press 2003.

[Fried–91
] J. Friedman, On the second eigenvalue and random walks in random
$d$
regular graphs, Combinatorica 11 (1991) 331–362.

[GodRo–01
] C. Godsil and G. Royle, Algebraic graph theory, Graduate Texts in Mathematics 207, Springer 2001.

[LovPl–86
] L. Lovász and M.D. Plummer, Matching theory, Annals Discrete Math. 29, North Holland, 1986.

[Lubot–94
] A. Lubotzky, Discrete groups, expanding graphs and invariant measure, Birkhäuser 1994.

[LuPhS–88
] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8, 1988, pages 261–277.

[Margu–88
] G.A. Margulis, Explicit grouptheoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators, J. Probl. Inf. Transm 24, 1988, pages 39–46.

[Sarna–90
] P. Sarnak, Some applications of modular forms, Cambridge University Press 1990.

[Valet–97
] A. Valette, Graphes de Ramanujan et applications, Séminaire Bourbaki, exposé 829, Astérisque, 245, Soc. Math. France 1997, pages 247–296.

[West–01
] D.B. West, Introduction to graph theory, second edition, Prentice Hall 2001.