Spectra of the Mycielskian of a Signed Graph and Related Products

Abstract

In a search for graphs with arbitrarily large chromatic number, Mycielski has offered a construction that transforms a graph $G=(V,E)$ into a new graph $\mu(G)$, which is called the Mycielskian of $G$. Recently, the same concept is transferred to the framework of signed graphs. Accordingly, if $V=\{v_1, v_2,\ldots, v_n\}$ and $E=\{e_1, e_2,\ldots, e_n\}$, then the vertex set of $\mu(G)$ is the disjoint union of $V$, $V^{\prime}=\{v_1^{\prime},v_2^{\prime},\ldots,v_n^{\prime}\}$ and an isolated vertex $w$, and its edge set is $E \cup \{v_i^{\prime}v_j : v_iv_j \in E \} \cup \{v_i^{\prime}w : v_i^{\prime} \in V^{\prime} \}$. The Mycielskian of a signed graph $\Sigma=(G,\sigma)$ is the signed graph $\mu(\Sigma)=(\mu(G),\sigma_{\mu})$, where the signature $\sigma_{\mu}$ is defined as $\sigma_{\mu}(v_iv_j)=\sigma_{\mu}(v_i^\prime v_j)=\sigma(v_iv_j)$ and $\sigma_{\mu}(v_i^\prime w)=1$. In this paper, we compute the characteristic polynomial of the adjacency matrix of $\mu(\Sigma)$, and extract the entire spectrum as well as the Laplacian spectrum, the net Laplacian spectrum and the normalized Laplacian spectrum, when $\Sigma$ satisfies particular regularity conditions. For the signed graphs $\Sigma_1$ and $\Sigma_2$, we introduce three products based on $\mu(\Sigma_1)$. For each of them, we compute the characteristic polynomial of the adjacency matrix or the Laplacian matrix, and extract the corresponding spectra either in general case or in particular case imposing regularity conditions for both constituents. As an application, we construct infinitely many pairs of switching non-isomorphic signed graphs that share the same spectrum or the Laplacian spectrum. Finally, we compute the Kirchhoff index and the number of spanning trees of $\mu(\Sigma)$ and every product, whenever the constituents are ordinary connected regular graphs.