In this talk we present the main topics, research questions and the expected results of the proposed PhD thesis.

In the PhD Thesis we will focus on open questions and problems which concern the Cage problem and the Degree/Diameter problem for undirected and directed graphs.

Cage Problem (Degree/Girth Problem): Given natural numbers k and g, find the smallest possible number of vertices n(k,g) in a graph of degree k and girth g.

Degree/Diameter Problem: Given natural numbers k and d, find the largest possible number of vertices n(k,d) in a graph of maximum degree k and diameter d.

(Directed) Degree/Diameter Problem: Given natural numbers d and k, find the largest possible number of vertices n_{d,k} in a digraph of maximum out-degree d and diameter k.

In the first part of the PhD thesis we will focus on the bipartite graphs of excess 4, antipodal cages of even girth and small excess and on the excess of the vertex-transitive graphs. We plan to prove the non-existence of infinitely many bipartite (k,g)-graphs of excess 4, the non-existence of almost all potential antipodal cages of even girth and small excess and to improve the Biggs’s result which address the existence of the vertex-transitive graphs of given degree and girth.

In the second part we will focus on the Bermond and Bollob\’ as question: “Given a positive integer c>0, does there exist a pair k and d, such that n(k,d)\leq M(k,d)-c?,” where M(k,d) is the Moore bound. We plan to answer this question combining spectral and real analysis.

In the last part of the PhD thesis we will focus on two problems which concern the degree/diameter problem for directed graphs. We plan to answer the question about the monotonicity of the function n_{d,k} in k and d, and to prove the non-existence of infinitely many (d,k,\delta)-digraphs containing only self repeat vertices.