I am considering an undirected planar graph $\mathcal{G} = (E, V)$ with no loop. If necessary, we can assume that there are no node of degree one. It is however not excluded that there are multiple vertices between two nodes. I now choose a node $v$. I would like to find the number of simple paths that go from $v$ to $v$, i.e., the number of walks starting and ending at $v$ that don't go through any vertex more than once.

For the purpose of the illustration, Consider: enter image description here

This graph has $6$ different paths connecting $v = 1$ to itself.

I found a non-polynomial time algorithm to count these paths, but I would like to find a formula for this.

  • 1
    $\begingroup$ But you wrote "with no loop" while your illustration has one. Can you give an illustration of what you actually seek? $\endgroup$ – David G. Stork Dec 20 '18 at 0:35
  • 1
    $\begingroup$ @DavidG.Stork No, it has no loops, because a loop is an edge joining a vertex to itself. I think the question is correct. $\endgroup$ – Alex Ravsky Dec 20 '18 at 2:20
  • $\begingroup$ Yes, @DavidG.Stork, you are right. I allow the graph to have multiple vertices between two nodes (as in the example I gave) but no loops. $\endgroup$ – V. Goepp Dec 21 '18 at 16:12

Given a vertex $v$ of a graph $\mathcal G$ a walk starting and ending at $v$ that don't going through any vertex of $\mathcal G$ more than once we’ll call a $v$-cycle.

I found a non-polynomial time algorithm to count these paths,

If $\mathcal G$ is $n$-gon in which there are $a_i$ instances of $i$-th edge of $n$-gon, then for each vertex $v$ of $\mathcal G$ there is exactly $\prod a_i$ $v$-cycles of non-zero length. In particular, when all $a_i=2$ then the number of $v$-cycles if $2^{|E|/2}$. If we wish to have a graph without multiple edges with exponential lower bound for the number of $v$-cycles, then we can subdivide each second instance of a multiple edge by a vertex.

The remaining part of my answer is conjectural, and I’m going to think about it more later.

Nevertheless, I guess that that for each vertex $v$ of a planar graph $\mathcal G$ without multiple edges there is at most exponentially many $v$-cycles in $\mathcal G$. This claim also may imply that for each vertex $v$ of a planar graph $\mathcal G$ there is at most exponentially of $|E|$ many $v$-paths in $\mathcal G$.

In order to prove this conjecture, for the simplicity if necessary, we can assume that there are no node of degree one, because such a node cannot belong to any cycle. Next we associate the graph $\mathcal G$ with its arbitrary plane drawing. Then I guess that each cycle of $\mathcal G$ is uniquely determined by a set of faces which it bounds. Since $\mathcal G$ has $O(|E|)$ faces, there are at most $2^{O(|E|)}$ cycles in $\mathcal G$.

Also are interesting grid graphs. Let $v$ be the origin of an infinite square grid graph $\mathcal G$. I guess that the sets of faces of $\mathcal G$ bounded by $v$-cycles are exactly sets $S^*$ of vertices of the dual graph $\mathcal G^*=(V^*,E^*)$ such $v$ has and incident face both in $S^*$ and $V^*\setminus S^*$ and both subgraph induced on $S^*$ and $V^*\setminus S^*$ are connected. Since the dual $G^*$ is again an infinite square grid graph, it turns out that we went close to a recent percolation related counting problem. Namely, we have to count a number of sets $S^*$ of the graph $\mathcal G$ such that induced by $S^*$ subgraph of $\mathcal G$ is connected (that is fixed a polyominoes) without holes and $S^*$ contains at least one and at most three faces of four faces of $\mathcal G$ incident to $v$. I expect that there exists exponentially many such sets $S^*$. Then for grid graphs we should have exponentially many $v$-cycles of a given length. I expect that there are still exponentially many $v$-cycles even when $\mathcal G$ is a rectangular grid and the $v$-cycle should contain all vertices of $\mathcal G$. The number of $v$-cycles is the number of Hamiltonian cycles, which are known as rook cycles, see also this related question. I guess that for sufficiently wide grids there are exponentially many rook cycles.


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.