In 1975, P. Erd\H os proposed the problem of determining the maximum number $f(n)$ of edges in a graph on $n$ vertices in which any two cycles are of different lengths. Let $f^{\ast}(n)$ be the maximum number of edges in a simple graph on $n$ vertices in which any two cycles are of different lengths. Let $M_n$ be the set of simple graphs on $n$ vertices in which any two cycles are of different lengths and with the edges of $f^{\ast}(n)$. Let $mc(n)$ be the maximum cycle length for all $G \in M_n$. In this paper, it is proved that for $n$ sufficiently large, $mc(n)\leq \frac{15}{16}n.$ \par We make the following conjecture: \par \bigskip \noindent{\bf Conjecture.} $$\lim_{n \rightarrow \infty} {mc(n)\over n}= 0.$$

We introduce the notion of Bonnet-Myers and Lichnerowicz sharpness in the Ollivier Ricci curvature sense. Our main result is a classification of all self-centered Bonnet-Myers sharp graphs (hypercubes, cocktail party graphs, even-dimensional demi-cubes, Johnson graphs , the Gosset graph J(2n, n) and suitable Cartesian products). We also present a purely combinatorial reformulation of this result. We show that Bonnet-Myers sharpness implies Lichnerowicz sharpness and classify all distance-regular Lichnerowicz sharp graphs under the additional condition θ_1=b_1-1. We also relate Bonnet-Myers sharpness to an upper bound of Bakry-Émery ∞-curvature, which motivates a general conjecture about Bakry-Émery ∞-curvature.

No abstract uploaded!

We associate to a finite digraph D a lattice polytope PD whose vertices are the rows of the Laplacian matrix of D. This generalizes a construction introduced by Braun and the third author. As a consequence of the Matrix-Tree Theorem, we show that the normalized volume of PD equals the complexity of D, and PD contains the origin in its relative interior if and only if D is strongly connected. Interesting connections with other families of simplices are established and then used to describe reflexivity, the h∗-polynomial, and the integer decomposition property of PD in these cases. We extend Braun and Meyer’s study of cycles by considering cycle digraphs. In this setting, we characterize reflexivity and show there are only four non-trivial reflexive Laplacian simplices having the integer decomposition property.

We investigate quantum graphs with infinitely many vertices and edges without the common restriction on the geometry of the underlying metric graph that there is a positive lower bound on the lengths of its edges. Our central result is a close connection between spectral properties of a quantum graph and the corresponding properties of a certain weighted discrete Laplacian on the underlying discrete graph. Using this connection together with spectral theory of (unbounded) discrete Laplacians on infinite graphs, we prove a number of new results on spectral properties of quantum graphs. Namely, we prove several self-adjointness results including a Gaffney-type theorem. We investigate the problem of lower semiboundedness, prove several spectral estimates (bounds for the bottom of spectra and essential spectra of quantum graphs, CLR-type estimates) and study spectral types.