3
$\begingroup$

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

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

2 Answers 2

2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Yes! This is exactly the first construction. Thanks! $\endgroup$
    – user3409
    Nov 9, 2013 at 17:49
  • $\begingroup$ Is this related to some kind of voltage graph? $\endgroup$
    – user3409
    Nov 9, 2013 at 18:02
  • $\begingroup$ I am afraid I do not know. Ben's remarks about blowups may lead somewhere... $\endgroup$ Nov 9, 2013 at 18:59
  • 1
    $\begingroup$ 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). $\endgroup$ Nov 10, 2013 at 4:07
  • $\begingroup$ @SimoneSeverini: Daniel is correct: You should unaccept this so that it is clear your question is not yet answered. $\endgroup$ Nov 10, 2013 at 11:52
1
$\begingroup$

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.)

The first construction applied to C_5

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.)

$\endgroup$
5
  • $\begingroup$ @ 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. $\endgroup$
    – user3409
    Nov 9, 2013 at 17:17
  • $\begingroup$ @ Ben Barber: Please see the drawing of Joseph. $\endgroup$
    – user3409
    Nov 9, 2013 at 17:49
  • $\begingroup$ @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. $\endgroup$
    – Ben Barber
    Nov 9, 2013 at 17:59
  • $\begingroup$ @ Ben Barber: I see now. Thanks. Have you seen these constructions before? $\endgroup$
    – user3409
    Nov 9, 2013 at 18:15
  • $\begingroup$ 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). $\endgroup$
    – Ben Barber
    Nov 9, 2013 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.