# Two graph constructions: new, old?

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$?

• "Do you like them?" in the title strikes me as a pretty strange question. Might we change it? – Todd Trimble Nov 9 '13 at 13:19
• Start of 2nd paragraph: But $G'$ has extra vertices... I think you mean edges. – Chris Godsil Nov 9 '13 at 14:00
• @ Chris Godsil: Yes Chris, thanks. Corrected. – user3409 Nov 9 '13 at 14:23

As a public service, so to speak, here is $C'_4$, if I've followed the construction correctly:

• Yes! This is exactly the first construction. Thanks! – user3409 Nov 9 '13 at 17:49
• Is this related to some kind of voltage graph? – user3409 Nov 9 '13 at 18:02
• I am afraid I do not know. Ben's remarks about blowups may lead somewhere... – Joseph O'Rourke Nov 9 '13 at 18:59
• Perhaps it would be better to edit this picture into the question? It seems misleading for it to be an accepted answer (the question hasn't been answered by anyone yet). – Daniel Moskovich Nov 10 '13 at 4:07
• @SimoneSeverini: Daniel is correct: You should unaccept this so that it is clear your question is not yet answered. – Joseph O'Rourke Nov 10 '13 at 11:52

Here's a picture of the result of applying the first construction (as I understand it) to $C_5$. The black vertices are the original vertices of $C_5$, and the colours are only to help see where the new edges and vertices came from. (Colouring in this way would make less sense if the original graph was less symmetric.)

So this is like a blow-up where each vertex is replaced by a clique of order $d(i)+1$, except only some of the edges have been included between the cliques.

The second construction is very nearly a genuine blow-up, the difference being that if two neighbours $y$ and $z$ of $x$ are adjacent in $G$, then then the cliques corresponding to $y$ and $z$ will be missing an edge between them. (This is a result of the "in different stars" restriction of the second construction.)

• @ Ben Barber: Thanks. Not exactly. Sorry, it means that my definitions are not clear enough. I will now draw an example and post it here. – user3409 Nov 9 '13 at 17:17
• @ Ben Barber: Please see the drawing of Joseph. – user3409 Nov 9 '13 at 17:49
• @SimoneSeverini Checking isomorphism is a hard problem (!), but I think our interpretations of the construction are the same. Joseph O'Rourke's red edges are my red and blue edges, his blue edges are my black edges, and his pink vertices are my black vertices. – Ben Barber Nov 9 '13 at 17:59
• @ Ben Barber: I see now. Thanks. Have you seen these constructions before? – user3409 Nov 9 '13 at 18:15
• I'm afraid not. The best I can say is that, if $G$ is triangle-free, then the second construction is just a blow-up (which is very common). – Ben Barber Nov 9 '13 at 18:32