Let $G$ be a connected graph of order $n$ and $U$ a unicyclic graph with the same order. We firstly give a sharp bound for $m_G\left(\mu \right)$, the multiplicity of a Laplacian eigenvalue $\mu$ of $G$. As a straightforward result, $m_U\left(1\right)\le n-2$. We then provide two graph operations (i.e., grafting and shifting) on graph $G$ for which the value of $m_G\left(1\right)$ is nondecreasing. As applications, we get the distribution of $m_U\left(1\right)$ for unicyclic graphs on $n$ vertices. Moreover, for the two largest possible values of $m_U\left(1\right)\in \{n-5,n-3\}$, the corresponding graphs $U$ are...

Let $G=(V,E)$, $V=\{v_1,v_2,...,v_n\}$, be a simple connected graph with $n$ vertices, $m$ edges and a sequence of vertex degrees $d_1\ge d_2\ge \cdots \ge d_n$. Denote by $A$ and $D$ the adjacency matrix and diagonal vertex degree matrix of $G$, respectively. The signless Laplacian of $G$ is defined as $L^{+}=D+A$ and the normalized signless Laplacian matrix as ${ℒ}^{+}=D^{-1/2}{L}^{+}{D}^{-1/2}$. The normalized signless Laplacian spreads of a connected nonbipartite graph $G$ are defined as $r\left(G\right)={\gamma }_2^{+}/{\gamma }_n^{+}$ and $l\left(G\right)={\gamma }_2^{+}-{\gamma }_n^{+}$, where ${\gamma }_1^{+}\ge {\gamma }_2^{+}\ge \cdots \ge {\gamma }_n^{+}\ge 0$ are eigenvalues of ${ℒ}^{+}$. We establish sharp lower and upper bounds for the normalized signless...

Let $G$ be a simple connected graph with vertex set $V\left(G\right)=\{v_1,v_2,\cdots ,v_n\}$ and edge set $E\left(G\right)$, and let $d_{v_i}$ be the degree of the vertex $v_i$. Let $D\left(G\right)$ be the distance matrix and let $T_r\left(G\right)$ be the diagonal matrix of the vertex transmissions of $G$. The generalized distance matrix of $G$ is defined as $D_{\alpha }\left(G\right)=\alpha T_r\left(G\right)+(1-\alpha )D\left(G\right)$, where $0\le \alpha \le 1$. Let ${\lambda }_1\left(D_{\alpha }\left(G\right)\right)\ge {\lambda }_2\left(D_{\alpha }\left(G\right)\right)\ge ...\ge {\lambda }_n\left(D_{\alpha }\left(G\right)\right)$ be the generalized distance eigenvalues of $G$, and let $k$ be an integer with $1\le k\le n$. We denote by $S_k\left(D_{\alpha }\left(G\right)\right)={\lambda }_1\left(D_{\alpha }\left(G\right)\right)+{\lambda }_2\left(D_{\alpha }\left(G\right)\right)+...+{\lambda }_k\left(D_{\alpha }\left(G\right)\right)$ the sum of the $k$ largest generalized distance eigenvalues. The generalized distance spread of a graph $G$ is defined as $D_{\alpha }S\left(G\right)={\lambda }_1\left(D_{\alpha }\left(G\right)\right)-{\lambda }_n\left(D_{\alpha }\left(G\right)\right)$....

The imbalance of an edge $e=\{u,v\}$ in a graph is defined as $i\left(e\right)=\left|d\right(u)-d(v\left)\right|$, where $d(·)$ is the vertex degree. The irregularity $I\left(G\right)$ of $G$ is then defined as the sum of imbalances over all edges of $G$. This concept was introduced by Albertson who proved that $I\left(G\right)\le 4n^3/27$ (where $n=\left|V\right(G\left)\right|$) and obtained stronger bounds for bipartite and triangle-free graphs. Since then a number of additional bounds were given by various authors. In this paper we prove a new upper bound, which improves a bound found by Zhou and Luo in 2008. Our bound involves...

Let $\left\{X_{ij}\right\}$, $i,j=\cdots$, be a double array of independent and identically distributed (i.i.d.) real random variables with $E{X}_{11}=\mu$, $E|X_{11}{-\mu |}^2=1$ and $E|X_{11}{|}^{4}lt;\infty$. Consider sample covariance matrices (with/without empirical centering) $𝒮=\frac{1}{n}{\sum }_{j=1}^n({𝐬}_j-\overline{𝐬}){({𝐬}_j-\overline{𝐬})}^T$ and $𝐒=\frac{1}{n}{\sum }_{j=1}^n{𝐬}_j{𝐬}_j^T$, where $\overline{𝐬}=\frac{1}{n}{\sum }_{j=1}^n{𝐬}_j$ and ${𝐬}_j={𝐓}_n^{1/2}{(X_{1j},...,X_{pj})}^T$ with ${\left({𝐓}_n^{1/2}\right)}^2={𝐓}_n$, non-random symmetric non-negative definite matrix. It is proved that central limit theorems of eigenvalue statistics of $𝒮$ and $𝐒$ are different as $n\to \infty$ with $p/n$ approaching a positive constant. Moreover, it is also proved that such a different behavior is not observed in the...

For a simple graph $G$ on $n$ vertices and an integer $k$ with $1\le k\le n$, denote by ${𝒮}_k^{+}\left(G\right)$ the sum of $k$ largest signless Laplacian eigenvalues of $G$. It was conjectured that ${𝒮}_k^{+}\left(G\right)\le e\left(G\right)+\left(\genfrac{}{}{0pt}{}{k+1}{2}\right)$, where $e\left(G\right)$ is the number of edges of $G$. This conjecture has been proved to be true for all graphs when $k\in \{1,2,n-1,n\}$, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all $k$). In this note, this conjecture is proved to be true for all graphs when $k=n-2$, and for some new classes of graphs.

Let $a=(a_1,a_2,...,a_n)$ be a nonincreasing sequence of positive real numbers. Denote by $S=\{1,2,...,n\}$ the index set and by $J_k=\{I=\{r_1,r_2,...,r_k\}$, $1\le r_1<r_2<\cdots <r_k\le n\}$ the set of all subsets of $S$ of cardinality $k$, $1\le k\le n-1$. In addition, denote by $a_I=a_{r_1}+a_{r_2}+\cdots +a_{r_k}$, $1\le k\le n-1$, $1\le r_1<r_2<\cdots <r_k\le n$, the sum of $k$ arbitrary elements of sequence $a$, where $a_{I_1}=a_1+a_2+\cdots +a_k$ and $a_{I_n}=a_{n-k+1}+a_{n-k+2}+\cdots +a_n$. We consider bounds of the quantities $R{S}_k\left(a\right)=a_{I_1}/a_{I_n}$, $L{S}_k\left(a\right)=a_{I_1}-a_{I_n}$ and $S_{k,\alpha }\left(a\right)={\sum }_{I\in J_k}{a}_I^{\alpha }$ in terms of $A={\sum }_{i=1}^n{a}_i$ and $B={\sum }_{i=1}^n{a}_i^2$. Then we use the obtained results to generalize some results regarding Laplacian and normalized Laplacian eigenvalues of graphs.

Suppose that $A$ is a real symmetric matrix of order $n$. Denote by $m_A\left(0\right)$ the nullity of $A$. For a nonempty subset $\alpha$ of $\{1,2,...,n\}$, let $A\left(\alpha \right)$ be the principal submatrix of $A$ obtained from $A$ by deleting the rows and columns indexed by $\alpha$. When $m_{A\left(\alpha \right)}\left(0\right)=m_A\left(0\right)+\left|\alpha \right|$, we call $\alpha$ a P-set of $A$. It is known that every P-set of $A$ contains at most $\lfloor n/2\rfloor$ elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As...

In this paper, we study the size of the giant component $C_G$ in the random geometric graph $G=G(n,r_n,f)$ of $n$ nodes independently distributed each according to a certain density $f(·)$ in ${[0,1]}^2$ satisfying ${inf}_{x\in {[0,1]}^2}f\left(x\right)gt;$ $0$. If $\frac{c_1}{n}\le r_n^2\le c_2\frac{logn}{n}$ for some positive constants $c_1$, $c_2$ and $n{r}_n^2⟶\infty$ as $n\to \infty$, we show that the giant component of $G$ contains at least $n-\mathrm{o}\left(n\right)$ nodes with probability at least $1-{\mathrm{e}}^{-\beta n{r}_n^2}$ for all $n$ and for some positive constant $\beta$. We also obtain estimates on the diameter and number of the non-giant components of $G$.

The line graph of a graph $G$, denoted by $L\left(G\right)$, has $E\left(G\right)$ as its vertex set, where two vertices in $L\left(G\right)$ are adjacent if and only if the corresponding edges in $G$ have a vertex in common. For a graph $H$, define ${\overline{\sigma }}_2\left(H\right)=min\{d\left(u\right)+d\left(v\right):uv\in E\left(H\right)\}$. Let $H$ be a 2-connected claw-free simple graph of order $n$ with $\delta \left(H\right)\ge 3$. We show that, if ${\overline{\sigma }}_2\left(H\right)\ge \frac{1}{7}(2n-5)$ and $n$ is sufficiently large, then either $H$ is traceable or the Ryjáček’s closure $\mathrm{cl}\left(H\right)=L\left(G\right)$, where $G$ is an essentially $2$-edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10...

Consider a $N\times n$ non-centered matrix ${𝛴}_n$ with a separable variance profile: $${𝛴}_n=\frac{D_n^{1/2}{X}_n{\tilde{D}}_n^{1/2}}{\sqrt{n}}+A_n.$$ Matrices $D_n$ and ${\tilde{D}}_n$ are non-negative deterministic diagonal, while matrix $A_n$ is deterministic, and $X_n$ is a random matrix with complex independent and identically distributed random variables, each with mean zero and variance one. Denote by $Q_n\left(z\right)$ the resolvent associated to ${𝛴}_n{𝛴}_n^{*}$, i.e. $$Q_n\left(z\right)={\left({𝛴}_n{𝛴}_n^{*}-z{I}_N\right)}^{-1}.$$ Given two sequences of deterministic vectors $\left(u_n\right)$ and $\left(v_n\right)$ with bounded Euclidean norms, we study the limiting behavior of the random bilinear form:...

A graph $G$ is $H$-saturated if it contains no $H$ as a subgraph, but does contain $H$ after the addition of any edge in the complement of $G$. The saturation number, $\mathrm{sat}(n,H)$, is the minimum number of edges of a graph in the set of all $H$-saturated graphs of order $n$. We determine the saturation number $\mathrm{sat}(n,P_6+t{P}_2)$ for $n\ge \frac{10}{3}t+10$ and characterize the extremal graphs for $n>\frac{10}{3}t+20$.