Let $G=(V,E)$ be a simple, undirected graph. Let $|V(G)|=n$ and $|E(G)|=m$. We consider connected graphs only. We write $i\sim j$ if $i$ and $j$ form an edge. Let $N(i)=\{j:i\sim j\}$. We write $d(i)=|N(i)|$ for the degree of $i$. From $G$, we construct another graph $G^{\prime }$. For each vertex of $G$, we construct a star $K_{1,d\left( i\right) }^{i}$. Recall that a star $K_{1,l}$ is the graph with $l+1$ vertices: $l$ vertices have degree $1$; one vertex has degree $l$. In the star $K_{1,d\left( i\right) }^{i}$, the vertex of degree $d(i)$ is $i$ and the neighbours of $i$ have degree $1$. There are in total $n$ stars, each one with $d(i)+1$ vertices. Therefore, the total number of vertices of $G^{\prime }$ is
$$|V(G^{\prime })|=\sum\limits_{i}\left(d(i)+1\right)_{i}=2|E(G)|+|V(G)|=2m+n.$$
But $G^{\prime }$ has extra edges: we connect in $G^{\prime }$ all the vertices with the same label. It follows that $G^{\prime }$ has a clique of size $d(1)+1$, for each vertex $i$. Recall that a clique is a complete subgraph in a graph. The total number of edges of $G^{\prime }$ is
$$|E(G^{\prime })|=2|E(G)|+\sum\limits_{i}\binom{\left( d(i)+1\right) _{i}}{2}.$$
Let us give an example. Denote by $C_{n}$ the $n$-cycle: this is the connected graph with $n$ edges and all vertices of degree $2$. The neighbours of each vertex are then of the form $K_{1,2}$. There are a total of $n$ $K_{1,2}$ stars in $% C_{n}^{\prime }$. The total number of vertices is $3n$. The edges in the stars are $3n-n=2n$. For the second term in the sum on the right hand side of the above equation, we have $3n$. So, the total number of edges in $% C_{n}^{\prime }$ is $5n$.
The definition of $G^{\prime }$ suggests an alternative construction. We shall construct a graph $G^{\prime \prime }$ from $G$. Again, the construction is sub-divided into two parts: initially, we create vertices associated to neighbourhoods; then we connect vertices in different neighbourhoods. So, the first step is to get $n$ stars $K_{1,d\left( i\right) }^{i}$, with $i=1,2,...,n$. As before, each star corresponds to the vertices in $N(i)$, plus $i$ — where $i$ is the vertex of degree $d(i)$ in $% K_{1,d\left( i\right) }^{i}$. Then, two vertices in different stars are adjacent in $G^{\prime \prime }$ whenever they are adjacent in $G$.
Problem 1. This is not exactly a problem: do these graphs, $G^{\prime }$ and $% G^{\prime \prime }$, have a name in the literature? Any references please?
Problem 2. In case the answer is "no, these graphs have not been studied before", I would like to get some grip on their properties — and this is a research problem. Specifically, can we say anything about the spectra of the adjacency matrix of $G^{\prime }$ and $G^{\prime \prime }$, given the spectrum of the adjacency matrix of $G$?
