Laplacian Spectrum of Two Classes of \(\psi \)-Sum Graphs with Applications

Graph operation is an effective way to synthetize several kinds of big graphs from small factor graphs. Subdivided graph ( \(\text {S}(\Gamma )\) $\text{S}(\mathrm{\Gamma })$ ) is a graph obtained by adding a vertex to each edge of graph \(\Gamma \) $\mathrm{\Gamma }$ , while vertex-semi total graph ( \(R(\Gamma )\) $R(\mathrm{\Gamma })$ ) is the graph obtained by adding a new vertex corresponding to each edge of graph \(\Gamma \) $\mathrm{\Gamma }$ and joining the new vertex to the end vertices of the corresponding edge. Subdivided sum graph and vertex-semi total sum graph are two kinds of \(\psi \) $\psi$ -sum graphs generated by utilizing Cartesian product operation for \(\psi (\Gamma _1)\) $\psi ({\mathrm{\Gamma }}_1)$ and \(\Gamma _2\) ${\mathrm{\Gamma }}_2$ , denoted by \(\Gamma _1+_{\psi }\Gamma _2\) ${\mathrm{\Gamma }}_1{+}_{\psi }{\mathrm{\Gamma }}_2$ , where \(\psi \in \{S, R\}\) $\psi \in \{S,R\}$ . In this work, we establish the Laplacian spectrum of \(\Gamma _1+_S\Gamma _2\) ${\mathrm{\Gamma }}_1{+}_S{\mathrm{\Gamma }}_2$ and \(\Gamma _1+_R\Gamma _2\) ${\mathrm{\Gamma }}_1{+}_R{\mathrm{\Gamma }}_2$ of k-regular graph \(\Gamma _1\) ${\mathrm{\Gamma }}_1$ and any connected graph \(\Gamma _2\) ${\mathrm{\Gamma }}_2$ in terms of Laplacian spectrum of factor graphs. As applications, we determine the Kirchhoff index, global mean-first passage time and number of spanning trees of \(\Gamma _1+_S\Gamma _2\) ${\mathrm{\Gamma }}_1{+}_S{\mathrm{\Gamma }}_2$ and \(\Gamma _1+_R\Gamma _2\) ${\mathrm{\Gamma }}_1{+}_R{\mathrm{\Gamma }}_2$ , respectively.