This paper contains a number of results in the theory of star partitions of graphs. We illustrate a variety of situations which can arise when the Reconstruction Theorem for graphs is used, considering in particular galaxy graphs - these are graphs in which every star set is independent. We discuss a recursive ordering of graphs based on the Reconstruction Theorem, and point out the significance of galaxy graphs in this connection.

Let $W_n=K_1\vee C_{n-1}$ be the wheel graph on $n$ vertices, and let $S(n,c,k)$ be the graph on $n$ vertices obtained by attaching $n-2c-2k-1$ pendant edges together with $k$ hanging paths of length two at vertex $v_0$, where $v_0$ is the unique common vertex of $c$ triangles. In this paper we show that $S(n,c,k)$ ($c\ge 1$, $k\ge 1$) and $W_n$ are determined by their signless Laplacian spectra, respectively. Moreover, we also prove that $S(n,c,k)$ and its complement graph are determined by their Laplacian spectra, respectively, for $c\ge 0$ and $k\ge 1$.

In this paper we derive new properties complementary to an $2n\times 2n$ Brualdi-Li tournament matrix $B_{2n}$. We show that $B_{2n}$ has exactly one positive real eigenvalue and one negative real eigenvalue and, as a by-product, reprove that every Brualdi-Li matrix has distinct eigenvalues. We then bound the partial sums of the real parts and the imaginary parts of its eigenvalues. The inverse of $B_{2n}$ is also determined. Related results obtained in previous articles are proven to be corollaries.

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

The distance Laplacian of a connected graph $G$ is defined by $ℒ=\mathrm{Diag}\left(\mathrm{Tr}\right)-𝒟$, where $𝒟$ is the distance matrix of $G$, and $\mathrm{Diag}\left(\mathrm{Tr}\right)$ is the diagonal matrix whose main entries are the vertex transmissions in $G$. The spectrum of $ℒ$ is called the distance Laplacian spectrum of $G$. In the present paper, we investigate some particular distance Laplacian eigenvalues. Among other results, we show that the complete graph is the unique graph with only two distinct distance Laplacian eigenvalues. We establish some properties of the distance...

The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph $G$ with vertex set $V=\{v_1,v_2,\cdots ,v_n\}$, the extended double cover of $G$, denoted $G^{*}$, is the bipartite graph with bipartition $(X,Y)$ where $X=\{x_1,x_2,\cdots ,x_n\}$ and $Y=\{y_1,y_2,\cdots ,y_n\}$, in which $x_i$ and $y_j$ are adjacent iff $i=j$ or $v_i$ and $v_j$ are adjacent in $G$. In this paper we obtain formulas for the characteristic polynomial and the spectrum of $G^{*}$ in terms of the corresponding information of $G$. Three formulas are derived for the number of spanning trees in $G^{*}$ for a connected...