Page 325 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 325
SPECTRAL GRAPH THEORY (MS-46)
On the rank of pseudo walk matrices
Alexander Farrugia, alex.farrugia@um.edu.mt
G˙ .F. Abela Junior College, University of Malta, Malta
In the literature, the walk matrix Wb associated with a graph G having vertex set V(G) is
the matrix with columns b, Ab, A2b, . . . , Ar−1b that enumerates the number of all possible
walks on G of length 0, 1, 2, . . . , r − 1 starting from each vertex of G and ending at any of the
vertices indicated by b. We generalize walk matrices further to obtain pseudo walk matrices
Wv having any walk vector v. For any subset S of V(G) × V(G), the total number of walks
N0(S), N1(S), N2(S), . . . of length 0, 1, 2, . . . in G that start from vertex i and end at vertex j
for all (i, j) ∈ S is considered. Various results on such pseudo walk matrices are presented, par-
ticularly related to their rank. The matrix rank of pseudo walk matrices allows the consideration
of controllable and recalcitrant pairs.
The local spectra of a graph and some of their applications
Miquel Àngel Fiol Mora, miguel.angel.fiol@upc.edu
Universitat Politècnica de Catalunya, Spain
Given a graph Γ with vertex set V , the local spectrum of a vertex subset C ⊂ V is constituted
by the eigenvalues of Γ with local multiplicities, which are nonnegative real numbers (possibly
zero). The local spectrum of C gives information on the structure of the graph Γ when it is ‘seen’
from C. In particular, when C consists of a single vertex u, the local multiplicities of u sum up
to one, while the local multiplicities of a given eigenvalue λ, when added over all vertices, gives
the (standard) multiplicity of λ. The aim of this talk is to describe some applications of the local
spectra. For instance, they have been used in the characterization of distance-regular graphs,
completely regular codes, existence of some subgrafs of a distance-regular graph, identifying
vital nodes in complex networks, possible graph automorphisms, etc.
Keywords: Graph; Distance-regular graph, Complex network, Adjacency matrix, Adjacency
spectrum, Laplacian spectrum, Local eigenvalues; Local multiplicities.
2010 Mathematics Subject Classification: 05C50, 05C82, 05E30, 15A18, 94B25.
Maximal cliques in strongly regular graphs
Gary Greaves, gary@ntu.edu.sg
Nanyang Technological University, Singapore
In this talk, I will introduce a cubic polynomial that can be associated to a strongly regular graph
Γ. The roots of this polynomial give rise to upper and lower bounds for the size of a maximal
clique in Γ. I will explain how we can use this cubic polynomial to rule out the existence of
strongly regular graphs that correspond to an infinite family of otherwise feasible parameters.
This talk is based on joint work with Jack Koolen and Jongyook Park.
323
On the rank of pseudo walk matrices
Alexander Farrugia, alex.farrugia@um.edu.mt
G˙ .F. Abela Junior College, University of Malta, Malta
In the literature, the walk matrix Wb associated with a graph G having vertex set V(G) is
the matrix with columns b, Ab, A2b, . . . , Ar−1b that enumerates the number of all possible
walks on G of length 0, 1, 2, . . . , r − 1 starting from each vertex of G and ending at any of the
vertices indicated by b. We generalize walk matrices further to obtain pseudo walk matrices
Wv having any walk vector v. For any subset S of V(G) × V(G), the total number of walks
N0(S), N1(S), N2(S), . . . of length 0, 1, 2, . . . in G that start from vertex i and end at vertex j
for all (i, j) ∈ S is considered. Various results on such pseudo walk matrices are presented, par-
ticularly related to their rank. The matrix rank of pseudo walk matrices allows the consideration
of controllable and recalcitrant pairs.
The local spectra of a graph and some of their applications
Miquel Àngel Fiol Mora, miguel.angel.fiol@upc.edu
Universitat Politècnica de Catalunya, Spain
Given a graph Γ with vertex set V , the local spectrum of a vertex subset C ⊂ V is constituted
by the eigenvalues of Γ with local multiplicities, which are nonnegative real numbers (possibly
zero). The local spectrum of C gives information on the structure of the graph Γ when it is ‘seen’
from C. In particular, when C consists of a single vertex u, the local multiplicities of u sum up
to one, while the local multiplicities of a given eigenvalue λ, when added over all vertices, gives
the (standard) multiplicity of λ. The aim of this talk is to describe some applications of the local
spectra. For instance, they have been used in the characterization of distance-regular graphs,
completely regular codes, existence of some subgrafs of a distance-regular graph, identifying
vital nodes in complex networks, possible graph automorphisms, etc.
Keywords: Graph; Distance-regular graph, Complex network, Adjacency matrix, Adjacency
spectrum, Laplacian spectrum, Local eigenvalues; Local multiplicities.
2010 Mathematics Subject Classification: 05C50, 05C82, 05E30, 15A18, 94B25.
Maximal cliques in strongly regular graphs
Gary Greaves, gary@ntu.edu.sg
Nanyang Technological University, Singapore
In this talk, I will introduce a cubic polynomial that can be associated to a strongly regular graph
Γ. The roots of this polynomial give rise to upper and lower bounds for the size of a maximal
clique in Γ. I will explain how we can use this cubic polynomial to rule out the existence of
strongly regular graphs that correspond to an infinite family of otherwise feasible parameters.
This talk is based on joint work with Jack Koolen and Jongyook Park.
323
