Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking for a special kind of returning paths of length $L$ in cubic planar graphs with the property $\mathfrak E$, that when I write down the times a certain vertex is visited, no vertex has the same number of visits.

Def. A returning path $P=v_0v_1\dots v_nv_0$ of length $L$ on a graph is an $\mathfrak E_L$ path, if $|v_k|\neq |v_m|, \forall k,m$, where $|v_k|$ denotes the number of times $v_k$ is met.

Let me give a non-planar example: The complete graph $K_5$ (which is not cubic)
$\hskip1.7in$ 666

could provide the following path of length $15$: $P_{K_5}=ABCDE\;ABCD\;ABC\;AB\;A$. When sorted by visiting times I'll get:

$$ \begin{array}{c|c|c|c|c} A&B&C&D&E\\ \hline 5&4&3&2&1 \end{array} $$ or using visiting numbers as exponents, we can write it as: $A^5B^4C^3D^2E$, so $P$ has property $\mathfrak E_{15}$ in a kind of minimal way: Having $5$ different vertices met with $5$ different visiting times, you'll need at least $15$ steps.

Def. A path of given length $L$ is $\mathfrak E_L$ minimal on a graph $G$, if $\sum |v_k|$ is minimal.

Remark In the following the number of steps should match the number of vertices in the graph.

This minimum is obviously not reached in cubic planar graphs. My question is:

How could $\mathfrak E_L$ minimal paths on cubic planar graphs look like?

I think I found indications that walking on a straight line is the best we can do. Here's my idea, which lacks a proof: I'll stay with the $K_5$ example. Expand the vertex $A$ to a $4$-cycle $C_4$ with vertices $A_0$ to $A_3$.

$\hskip0.1in$enter image description here enter image description here

A cubic planar graph with this fragment, which is equivalent to three adjacent squares, could contain a path $P$ that will now look like: $$P_{\text{cubic,planar}}=A_0BCDEA_3A_2A_1A_0BCDA_2A_1A_0BCA_1A_0BA_0,$$ where I assume that $A_3$ and $A_0$ are not connected by another path shorter than three steps. I tried to indicate this with the dashed line. Resorting this path gives: $A_0 (A_0B)^4(A_1C)^3(A_2D)^2(A_3E)$, but now several vertices are met the same number of times, e.g. $A_1$ and $C$.

Therefore I thought about combining to upper and lower line (I mean combine $A_0$ and $B$, $A_1$ and $C$ and so forth...) to single line and just consider going back and forth this straight line. Starting from the right most point $A_3$, I'll get the resorted path $P_{L_4}$ to be $A_3^4 A_2^5A_1^3A_0 $, which can be generalized to $$ A_{n-1}^{-(n-1)}\prod_{k=0}^{n-1} A_k^{2k+1}. $$ The length of the paths will be $n^2-n+1$. So my question can be rephrased:

Are there $\mathfrak E_{n^2-n+1}$ minimal paths on cubic planar graphs other than the line graphs?


share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.