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?

$\hskip6.0in$$\color{white}{6666}$

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.