The Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph are the characteristic polynomials of its Laplacian matrix, signless Laplacian matrix and normalized Laplacian matrix, respectively. In this paper, we mainly derive six reduction procedures on the Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph which can be used to construct larger Laplacian, signless Laplacian and normalized Laplacian cospectral graphs, respectively....

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

In this paper we investigate the effect on the multiplicity of Laplacian eigenvalues of two disjoint connected graphs when adding an edge between them. As an application of the result, the multiplicity of 1 as a Laplacian eigenvalue of trees is also considered.

Let $G=(V,E)$ be a 3-connected planar graph, with $V=\{1,...,n\}$. Let $M=\left(m_{i,j}\right)$ be a symmetric $n\times n$ matrix with exactly one negative eigenvalue (of multiplicity 1), such that for $i,j$ with $i\ne j$, if $i$ and $j$ are adjacent then $m_{i,j}\<0$ and if $i$ and $j$ are nonadjacent then $m_{i,j}=0$, and such that $M$ has rank $n-3$. Then the null space $kerM$ of $M$ gives an embedding of $G$ in $S^2$ as follows: let $\{a,b,c\}$ be a basis of $kerM$, and for $i\in V$ let $\varphi \left(i\right):=(a_i,b_i,c_i{)}^T$; then $\varphi \left(i\right)\ne 0$, and $\psi \left(i\right):=\varphi \left(i\right)/\parallel \varphi \left(i\right)\parallel$ embeds $V$ in $S^2$ such that connecting, for any two adjacent vertices $i,j$, the points $\psi \left(i\right)$ and $\psi \left(j\right)$ by a shortest geodesic on $S^2$, gives...

As a generalization of the Sierpiński-like graphs, the subdivided-line graph Г(G) of a simple connected graph G is defined to be the line graph of the barycentric subdivision of G. In this paper we obtain a closed-form formula for the enumeration of spanning trees in Г(G), employing the theory of electrical networks. We present bounds for the largest and second smallest Laplacian eigenvalues of Г(G) in terms of the maximum degree, the number of edges, and the first Zagreb index of G. In addition,...

The zero forcing number and the positive zero forcing number of a graph are two graph parameters that arise from two types of graph colourings. The zero forcing number is an upper bound on the minimum number of induced paths in the graph that cover all the vertices of the graph, while the positive zero forcing number is an upper bound on the minimum number of induced trees in the graph needed to cover all the vertices in the graph. We show that for a block-cycle graph the zero forcing number equals...

Kragujevac (M. L. Kragujevac: On the Laplacian energy of a graph, Czech. Math. J. 56(131) (2006), 1207–1213) gave the definition of Laplacian energy of a graph $G$ and proved $LE\left(G\right)\ge 6n-8$; equality holds if and only if $G=P_n$. In this paper we consider the relation between the Laplacian energy and the chromatic number of a graph $G$ and give an upper bound for the Laplacian energy on a connected graph.