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

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

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

Let ${\mu }_{n-1}\left(G\right)$ be the algebraic connectivity, and let ${\mu }_1\left(G\right)$ be the Laplacian spectral radius of a $k$-connected graph $G$ with $n$ vertices and $m$ edges. In this paper, we prove that $${\mu }_{n-1}\left(G\right)\ge \frac{2n{k}^2}{(n(n-1)-2m)(n+k-2)+2k^2},$$ with equality if and only if $G$ is the complete graph $K_n$ or $K_n-e$. Moreover, if $G$ is non-regular, then $${\mu }_1\left(G\right)<2\Delta -\frac{2(n\Delta -2m)k^2}{2(n\Delta -2m)(n^2-2n+2k)+n{k}^2},$$ where $\Delta$ stands for the maximum degree of $G$. Remark that in some cases, these two inequalities improve some previously known results.

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.

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

We give a graph theoretic interpretation of $r$-Lah numbers, namely, we show that the $r$-Lah number ${⌊\genfrac{}{}{0pt}{}{n}{k}⌋}_r$ counting the number of $r$-partitions of an $(n+r)$-element set into $k+r$ ordered blocks is just equal to the number of matchings consisting of $n-k$ edges in the complete bipartite graph with partite sets of cardinality $n$ and $n+2r-1$ ($0\le k\le n$, $r\ge 1$). We present five independent proofs including a direct, bijective one. Finally, we close our work with a similar result for $r$-Stirling numbers of the second kind. ...

A graph $G=(V,E)$ is called improperly $(d_1,\cdots ,d_k)$-colorable if the vertex set $V$ can be partitioned into subsets $V_1,\cdots ,V_k$ such that the graph $G\left[V_i\right]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1\le i\le k$. In this paper, we mainly study the improper coloring of $1$-planar graphs and show that $1$-planar graphs with girth at least $7$ are $(2,0,0,0)$-colorable.

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let $G$ be a bridgeless simple graph with minimum degree at least $3$. Jackson and Yoshimoto (2007) showed that $G$ has an even factor containing two arbitrary prescribed edges. They also proved that $G$ has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges $e_1$ and $e_2$ of $G$, there is an even factor containing $e_1$ and $e_2$...

The generalized $k$-connectivity ${\kappa }_k\left(G\right)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as ${\lambda }_k\left(G\right)=min\{\lambda \left(S\right):S\subseteq V\left(G\right)$ and $\left|S\right|=k\}$, where $\lambda \left(S\right)$ denotes the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,...,T_{\ell }$ in $G$ such that $S\subseteq V\left(T_i\right)$ for $1\le i\le \ell$. In this paper we prove that for any two connected graphs $G$ and $H$ we have ${\lambda }_3(G\square H)\ge {\lambda }_3\left(G\right)+{\lambda }_3\left(H\right)$, where $G\square H$ is the Cartesian product of $G$ and $H$. Moreover, the bound is sharp. We also...