4
$\begingroup$

Disclaimer: I am not a professional graph theorist.

Motivation:

Let's consider the set $G_N$ of graphs with $N$ vertices where the vertices are assumed to be distinguishable. This set may correspond to the state space of a biological network whose connectivity varies over time or the set of potential social networks among a community of $N$ individuals.

The cardinality of $G_N$ is given by:

\begin{equation} \lvert G_N \rvert = \sum_{k=0}^{ N \choose 2} { { N \choose 2} \choose k} = 2^{{ N \choose 2}} \tag{1} \end{equation}

I observed that $\lvert G_N \rvert$ very quickly becomes astronomical:

\begin{equation} \forall N > 50, \lvert G_N \rvert > 10^{368} \tag{2} \end{equation}

which is many times greater than the number of atoms in the universe. For this reason, I wondered whether there might be a natural way to organise these graphs. One approach that occurred to me was to think of 'Hamiltonian paths' on the space of graphs.

Question:

If $G^k_N \subset G_N$ denotes the set of graphs with $N$ vertices with exactly $k$ edges:

\begin{equation} \lvert G^k_N \rvert = { { N \choose 2} \choose k} \tag{3} \end{equation}

my question is whether we can index the elements of $G^k_N$ so we have $G^k_N = \{\Gamma_i \}_{i=1}^{{ { N \choose 2} \choose k}}$ and $\Gamma_i$ and $\Gamma_{i \pm 1}$ differ by at most one edge i.e. all edges are the same except one which is relocated.

We can think of this as a Hamiltonian path because there is an edge between each element of $G^k_N$ and each element of $G^k_N$ occurs exactly once.

Note: For $G^k_N$ where $k\in \{0,1,{ N \choose 2}-1,{ N \choose 2} \}$ this proposition is certainly true.

$\endgroup$
  • 2
    $\begingroup$ Hm, this power of 2 counts all graphs, not only planar? $\endgroup$ – Fedor Petrov Jun 25 at 9:20
  • $\begingroup$ @FedorPetrov Thanks for pointing this out. $\endgroup$ – Aidan Rocke Jun 25 at 9:22
  • $\begingroup$ If you go from one graph to another that “differs in one edge” then they can’t both have $k$ edges, can they? $\endgroup$ – Gordon Royle Jun 25 at 11:26
  • $\begingroup$ @GordonRoyle I just clarified the question. I meant that all edges are the same except one which is relocated. $\endgroup$ – Aidan Rocke Jun 25 at 11:33
2
$\begingroup$

If you are talking about labelled graphs (distinguishable vertices) then the fact that these are graphs is irrelevant.

So you are really asking if there is a Hamilton path through all the $k$-subsets of an arbitrary $\binom{N}{2}$ set where two sets are adjacent if their symmetric difference has size two.

These are many such Hamilton paths, even Hamilton cycles, known under the general term "combinatorial Gray code".

Look up Carla Savage's survey of combinatorial Gray codes.

$\endgroup$
  • 2
    $\begingroup$ The original title mentioned planar graphs. Any thoughts on a Hpath through the relevant subset (k edges on N labeled vertices)? I suspect the answer is no. Gerhard "Has To Do With Triangles" Paseman, 2019.06.25. $\endgroup$ – Gerhard Paseman Jun 25 at 18:49
  • $\begingroup$ Well, it is known that we can move from any unlabelled planar triangulation to any other via a sequence of "edge flips" which are operations where an edge $xy$ is removed, thereby creating a 4-face, say $\mathit{xayb}$, and then the edge $ab$ is inserted, restoring the property of being a planar triangulation. After 30 seconds thought, it seems to me that triangulations will be the hardest to deal with, so I'll put my money on yes. $\endgroup$ – Gordon Royle Jun 26 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.