Spectra of strongly Deza graphs

A Deza graph G with parameters $(n,k,b,a)$ is a k-regular graph with n vertices such that any two distinct vertices have b or a common neighbours. The children $G_A$ and $G_B$ of a Deza graph G are defined on the vertex set of G such that every two distinct vertices are adjacent in $G_A$ or $G_B$ if and only if they have a or b common neighbours, respectively. A strongly Deza graph is a Deza graph with strongly regular children. In this paper we give a spectral characterisation of strongly Deza graphs, show relationships between eigenvalues, and study strongly Deza graphs which are distance-regular.     

Graphs determined by their Aα-spectra

Let $G$ be a graph with $n$ vertices, and let $A\left(G\right)$ and $D\left(G\right)$ denote respectively the adjacency matrix and the degree matrix of $G$. Define $A_{\alpha }\left(G\right)=\alpha D\left(G\right)+(1?\alpha )A\left(G\right)$for any real $\alpha \in [0,1]$. The collection of eigenvalues of $A_{\alpha }\left(G\right)$ together with multiplicities are called the $A_{\alpha }$-spectrum of $G$. A graph $G$ is said to be determined by its $A_{\alpha }$-spectrum if all graphs having the same $A_{\alpha }$-spectrum as $G$ are isomorphic to $G$. We first prove that some graphs are determined by their $A_{\alpha }$-spectra for $0\le \alpha <1$, including the complete graph $K_n$, the union of cycles, the complement of the union of cycles, the union of copies of $K_2$ and $K_1$, the complement of the union of copies of $K_2$ and $K_1$, the path $P_n$, and the complement of $P_n$. Setting $\alpha =0$ or $\frac{1}{2}$, those graphs are determined by $A$- or $Q$-spectra. Secondly, when $G$ is regular, we show that $G$ is determined by its $A_{\alpha }$-spectrum if and only if the join $G\vee K_m$ ($m\ge 2$) is determined by its $A_{\alpha }$-spectrum for $\frac{1}{2}<\alpha <1$. Furthermore, we also show that the join $K_m\vee P_n$ ($m,n\ge 2$) is determined by its $A_{\alpha }$-spectrum for $\frac{1}{2}<\alpha <1$. In the end, we pose some related open problems for future study.     

On the local geometry of graphs in terms of their spectra

In this paper we consider the relation between the spectrum and the number of short cycles in large graphs. Suppose $G_1,G_2,G_3,\dots$ is a sequence of finite and connected graphs that share a common universal cover $T$ and such that the proportion of eigenvalues of $G_n$ that lie within the support of the spectrum of $T$ tends to 1 in the large $n$ limit. This is a weak notion of being Ramanujan. We prove such a sequence of graphs is asymptotically locally tree-like. This is deduced by way of an analogous theorem proved for certain infinite sofic graphs and unimodular networks, which extends results for regular graphs and certain infinite Cayley graphs.     

Monochromatic subgraphs in randomly colored graphons

Let $T(H,G_n)$ be the number of monochromatic copies of a fixed connected graph $H$ in a uniformly random coloring of the vertices of the graph $G_n$. In this paper we give a complete characterization of the limiting distribution of $T(H,G_n)$, when ${\left\{G_n\right\}}_{n\ge 1}$ is a converging sequence of dense graphs. When the number of colors grows to infinity, depending on whether the expected value remains bounded, $T(H,G_n)$ either converges to a finite linear combination of independent Poisson variables or a normal distribution. On the other hand, when the number of colors is fixed, $T(H,G_n)$ converges to a (possibly infinite) linear combination of independent centered chi-squared random variables. This generalizes the classical birthday problem, which involves understanding the asymptotics of $T(K_s,K_n)$, the number of monochromatic $s$-cliques in a complete graph $K_n$ ($s$-matching birthdays among a group of $n$ friends), to general monochromatic subgraphs in a network.     

Fractional chromatic numbers of tensor products of three graphs

The tensor product $(G_1,G_2,G_3)$ of graphs $G_1$, $G_2$ and $G_3$ is defined by $V(G_1,G_2,G_3)=V\left(G_1\right)\times V\left(G_2\right)\times V\left(G_3\right)$and $E(G_1,G_2,G_3)=\left\{\left((u_1,u_2,u_3),(v_1,v_2,v_3)\right):\left|\{i:(u_i,v_i)\in E\left(G_i\right)\}\right|\ge 2\right\}.$Let ${\chi }_f\left(G\right)$ be the fractional chromatic number of a graph $G$. In this paper, we prove that if one of the three graphs $G_1$, $G_2$ and $G_3$ is a circular clique, ${\chi }_f(G_1,G_2,G_3)=min\{{\chi }_f\left(G_1\right){\chi }_f\left(G_2\right),{\chi }_f\left(G_1\right){\chi }_f\left(G_3\right),{\chi }_f\left(G_2\right){\chi }_f\left(G_3\right)\}.$     

Higher Laplacians on pseudo-Hermitian symmetric spaces

One of the most fundamental operators studied in geometric analysis is the classical Laplace–Beltrami operator. On pseudo-Hermitian manifolds, higher Laplacians $L_m$ are defined for each positive integer m, where $L_1$ coincides with the Laplace–Beltrami operator. Despite their natural definition, these higher Laplacians have not yet been studied in detail. In this paper, we consider the setting of simple pseudo-Hermitian symmetric spaces, i.e., let $X=G/H$ be a symmetric space for a real simple Lie group G, equipped with a G-invariant complex structure. We show that the higher Laplacians $L_1,L_3,\dots ,L_{2r?1}$ form a set of algebraically independent generators for the algebra ${\mathbb{D}}_G(X)$ of G-invariant differential operators on X, where r denotes the rank of X. For higher rank, this is the first instance of a set of generators for ${\mathbb{D}}_G(X)$ defined explicitly in purely geometric terms, and confirms a conjecture of Engli? and Peetre, originally stated in 1996 for the class of Hermitian symmetric spaces.     

Domination game and minimal edge cuts

In this paper a relationship is established between the domination game and minimal edge cuts. It is proved that the game domination number of a connected graph can be bounded above in terms of the size of minimal edge cuts. In particular, if $C$ a minimum edge cut of a connected graph $G$, then ${\gamma }_g\left(G\right)\le {\gamma }_g(G?C)+2{\kappa }^{\prime }\left(G\right)$. Double-Staller graphs are introduced in order to show that this upper bound can be attained for graphs with a bridge. The obtained results are used to extend the family of known traceable graphs whose game domination numbers are at most one-half their order. Along the way two technical lemmas, which seem to be generally applicable for the study of the domination game, are proved.     

A note on the weak (2,2)-Conjecture

Let $G=(V,E)$ be any graph without isolated edges. The well known 1–2–3 Conjecture asserts that the edges of $G$ can be weighted with $1,2,3$ so that adjacent vertices have distinct weighted degrees, i.e. the sums of their incident weights. It was independently conjectured that if $G$ additionally has no isolated triangles, then it can be edge decomposed into two subgraphs $G_1,G_2$ which fulfil the 1–2–3 Conjecture with just weights 1,2, i.e. such that there exist weightings ${\omega }_i:E\left(G_i\right)\to \{1,2\}$ so that for every $uv\in E$, if $uv\in E\left(G_i\right)$ then $d_{{\omega }_i}\left(u\right)\ne d_{{\omega }_i}\left(v\right)$, where $d_{{\omega }_i}\left(v\right)$ denotes the sum of weights incident with $v\in V$ in $G_i$ for $i=1,2$. We apply the probabilistic method to prove that the known weakening of this so-called Standard (2,2)-Conjecture holds for graphs with minimum degree large enough. Namely, we prove that if $\delta \left(G\right)\ge 3660$, then $G$ can be decomposed into graphs $G_1,G_2$ for which weightings ${\omega }_i:E\left(G_i\right)\to \{1,2\}$ exist so that for every $uv\in E$, $d_{{\omega }_1}\left(u\right)\ne d_{{\omega }_1}\left(v\right)$ or $d_{{\omega }_2}\left(u\right)\ne d_{{\omega }_2}\left(v\right)$. In fact we prove a stronger result, as one of the weightings is redundant, i.e. uses just weight 1.     

The survival probability of critical and subcritical branching processes in finite state space Markovian environment

Let ${\left(Z_n\right)}_{n\ge 0}$ be a branching process in a random environment defined by a Markov chain ${\left(X_n\right)}_{n\ge 0}$ with values in a finite state space $\mathbb{X}$. Let ${\mathbb{P}}_i$ be the probability law generated by the trajectories of ${\left(X_n\right)}_{n\ge 0}$ starting at $X_0=i\in \mathbb{X}.$ We study the asymptotic behaviour of the joint survival probability ${\mathbb{P}}_i\left(Z_n>0,X_n=j\right)$, $j\in \mathbb{X}$ as $n\to +\infty$ in the critical and strongly, intermediate and weakly subcritical cases.