In this note, we prove the sharp DaviesGaffneyGrigoryan Lemma for minimal heat kernels on graphs.

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 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.

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 study pretty good quantum state transfer (ie, state transfer that becomes arbitrarily close to perfect) between vertices of graphs with an involution in the presence of an energy potential. In particular, we show that if a graph has an involution that fixes at least one vertex or at least one edge, then there exists a choice of potential on the vertex set of the graph for which we get pretty good state transfer between symmetric vertices of the graph. We show further that in many cases, the potential can be chosen so that it is only non-zero at the vertices between which we want pretty good state transfer. As a special case of this, we show that such a potential can be chosen on the endpoints of a path to induce pretty good state transfer in paths of any length. This is in contrast to the result of [6], in which the authors show that there cannot be perfect state transfer in paths of length 4 or more, no matter what potential is chosen.

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.

We prove a homology vanishing theorem for graphs with positive Bakry-\'Emery curvature, analogous to a classic result of Bochner on manifolds\cite {Bochner}. Specifically, we prove that if a graph has positive curvature at every vertex, then its first homology group is trivial, where the notion of homology that we use for graphs is the path homology developed by Grigor'yan, Lin, Muranov, and Yau\cite {Grigoryan2}.%\Hm {added the fundamental group curvature relation} We moreover prove that the fundamental group is finite for graphs with positive Bakry-\'Emery curvature, analogous to a classic result of Myers on manifolds\cite {Myers1941}. The proofs draw on several separate areas of graph theory. We study graph coverings, gain graphs, and cycle spaces of graphs, in addition to the Bakry-\'Emery curvature and the path homology. The main results follow as a consequence of several different relationships developed among these different areas. Specifically, we show that a graph with positive curvature can have no non-trivial infinite cover preserving 3-cycles and 4-cycles, and give a combinatorial interpretation of the first path homology in terms of the cycle space of a graph. We relate cycle spaces of graphs to gain graphs with abelian gain group, and relate these to coverings of graphs. Along the way, we prove other new facts about gain graphs, coverings, and cycles spaces that are of related interest. Furthermore, we relate gain graphs to graph homotopy and the fundamental group developed by Grigor'yan, Lin, Muranov, and Yau\cite {Grigoryan_homotopy}, and obtain an alternative proof to their result that the abelianization of the fundamental

The set of all non-increasing nonnegative integers sequence $\pi=$ ($d(v_1 ),$ $d(v_2 ),$ $...,$ $d(v_n )$) is denoted by $NS_n$. A sequence $\pi\in NS_n$ is said to be graphic if it is the degree sequence of a simple graph $G$ on $n$ vertices, and such a graph $G$ is called a realization of $\pi$. The set of all graphic sequences in $NS_n$ is denoted by $GS_n$. A graphical sequence $\pi$ is potentially $H$-graphical if there is a realization of $\pi$ containing $H$ as a subgraph, while $\pi$ is forcibly $H$-graphical if every realization of $\pi$ contains $H$ as a subgraph. Let $K_k$ denote a complete graph on $k$ vertices. Let $K_{m}-H$ be the graph obtained from $K_{m}$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_{m}$). This paper summarizes briefly some recent results on potentially $K_{m}-G$-graphic sequences and give a useful classification for determining $\sigma(H,n)$.

No abstract uploaded!

No abstract uploaded!