Let $G$ be a finite simple graph with the vertex set $V$ and let $I_G$ be its edge ideal in the polynomial ring $S=𝕂\left[V\right]$. We compute the depth and the Castelnuovo-Mumford regularity of $S/I_G$ when $G=G_1\circ G_2$ or $G=G_1*G_2$ is a graph obtained from Cohen-Macaulay bipartite graphs $G_1$, $G_2$ by the $\circ$ operation or $*$ operation, respectively.

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

For each squarefree monomial ideal $I\subset S=k[x_1,...,x_n]$, we associate a simple finite graph $G_I$ by using the first linear syzygies of $I$. The nodes of $G_I$ are the generators of $I$, and two vertices $u_i$ and $u_j$ are adjacent if there exist variables $x,y$ such that $x{u}_i=y{u}_j$. In the cases, where $G_I$ is a cycle or a tree, we show that $I$ has a linear resolution if and only if $I$ has linear quotients and if and only if $I$ is variable-decomposable. In addition, with the same assumption on $G_I$, we characterize all squarefree monomial ideals...

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

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

Let $\Delta$ be a pure simplicial complex on the vertex set $\left[n\right]=\{1,...,n\}$ and $I_{\Delta }$ its Stanley-Reisner ideal in the polynomial ring $S=K[x_1,...,x_n]$. We show that $\Delta$ is a matroid (complete intersection) if and only if $S/I_{\Delta }^{\left(m\right)}$ ($S/I_{\Delta }^m$) is clean for all $m\in \mathbb{N}$ and this is equivalent to saying that $S/I_{\Delta }^{\left(m\right)}$ ($S/I_{\Delta }^m$, respectively) is Cohen-Macaulay for all $m\in \mathbb{N}$. By this result, we show that there exists a monomial ideal $I$ with (pretty) cleanness property while $S/I^m$ or $S/I^{\left(m\right)}$ is not (pretty) clean for all integer $m\ge 3$. If $dim\left(\Delta \right)=1$, we also prove that $S/I_{\Delta }^{\left(2\right)}$ ($S/I_{\Delta }^2$) is clean if and only...

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

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

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.

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

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

Given a graph $G$, let $f\left(G\right)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f\left(G\right)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. In this paper we prove that $f(m,{\theta }_{k,s})\ge \frac{1}{2}m+\Omega \left(m^{(2k+1)/(2k+2)}\right)$, which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write $K_k^{\text{'}}$ and $K_{t,s}^{\text{'}}$ for the subdivisions of $K_k$ and $K_{t,s}$. We show that $f(m,K_k^{\text{'}})\ge \frac{1}{2}m+\Omega \left(m^{(5k-8)/(6k-10)}\right)$ and $f(m,K_{t,s}^{\text{'}})\ge \frac{1}{2}m+\Omega \left(m^{(5t-1)/(6t-2)}\right)$, improving a result of Q. Zeng, J. Hou. We also give lower bounds on...