Definition: Let $G=(V,E)$ be a cubic (i.e. $3$-regular) graph, and $<$ a total order on $V$. For $v\in V$ let $v^\downarrow$ denote the set of nodes $w\in V$ such that $w<v$, and let $\alpha(v) = |N_v\cap v^\downarrow|$ be the number of neighbors of $v$ preceding $v$. For each $i$ let $D(i)$ denote the set of nodes $v\in V$ such that $\alpha(v)=i$. We say the ordering $<$ is strongly regular if $|D(0)| = 1$ and $|D(2)|\leqslant 1$.
Question: Does every connected cubic graph have a strongly regular ordering? If not, does every $3$-connected cubic Levi graph (i.e., bipartite graph of girth at least $6$) have a strongly regular ordering? What about $3$-connected cubic Hamiltonian graphs?
It's easy to show that any connected cubic graph has an ordering such that $|D(0)|=1$. A natural attempt to prove existence would hypothesize that $<$ is a total ordering that minimizes $|D(2)|$ among orderings with $|D(0)|=1$, but I wasn't able to deduce much from this.
Known special cases: It's not hard to come up with an explicit construction of a strongly regular ordering for any generalized Petersen graph.
Suppose $G$ has a Hamiltonian cycle $(v_1,v_2),...,(v_{n-1},v_n),(v_n,v_1)\in E$. A chordal cycle is a sequence of nodes $v_i,...,v_j$ such that $(v_i,v_j)\in E$ is a chord. We say $v_{i+1},...,v_{j-1}$ are the interior nodes in this cycle. A minimal chordal cycle is a chordal cycle such that no proper subsequence is a chordal cycle.
Proposition: If $G$ is $3$-connected and has a Hamiltonian cycle in which every node is contained in the interior of some minimal chordal cycle, then $G$ has a strongly regular ordering.
Proof: Let $(v_1,v_2),...,(v_{n-1},v_n),(v_n,v_1)\in E$ be such a Hamiltonian cycle. We define the ordering $w_1<...<w_n$ inductively starting with $w_1=v_1$. Suppose we've chosen $w_1,...,w_t$ such that $$W := \{w_1,...,w_t\} = \{v_i,v_{i+1},...,v_j\}$$ for some $v_i,v_j$, and $\alpha(w_s)$ is odd for $1<s\leqslant t$. If $v_{j+1} = v_{i-1}$ then we just set $w_n = v_{j+1}$ and we're done; the resulting order has $|D(2)|=0$. If $v_{j+1} = v_{i-2}$ then we set $w_{n-1} = v_{j+1}$ and $w_n= v_{i-1}$; the resulting order has $|D(2)|=1$. If $|N_{v_{j+1}}\cap W|$ is odd we can set $w_{t+1}=v_{j+1}$ and reiterate.
Thus we can assume $v_{j+1},...,v_{i-1}$ has non-empty interior and $|N_{v_{j+1}}\cap W|$ is even. Since $v_j\in N_{v_{j+1}}\cap W$ we must have $|N_{v_{j+1}}\cap W|=2$. Since $v_{j+2}\notin W$, the only way this can happen is if the chord adjacent to $v_{j+1}$ is adjacent to some node $v_k\in W$.
Let $v_\ell,...,v_m$ be a minimal chordal cycle containing $v_{j+1}$ in its interior. Since $v_k,...,v_{j+1}$ is a chordal cycle and $j+1<m$, we must have $v_k < v_\ell$ by minimality. But then $v_\ell\in\{v_{k+1},...,v_j\}\subseteq W$. Now let $s>j+1$ be minimal such that the chord adjacent to $v_s$ has its other end in $W$. Note that $v_s$ exists and $v_s\neq v_{i-1}$ since otherwise removing $v_{i-1}$ and $v_{j+1}$ would disconnect $G$ (this is where we use $v_{j+1}\neq v_{i-2}$). Thus $v_{s-1},v_{s+1}\notin W$ but the chordal neighbor of $v_s$ is in $W$, so $|N_{v_s}\cap W|=1$. Also we must have $s\leqslant m$ by minimality of $s$. We define $w_{t+1}=v_s$, $w_{t+2}=v_{s-1}$, ..., $w_{t'} = v_{j+1}$. We know $\alpha(w_{t+1})=1$, and $\alpha(w_{t''})>0$ for all $t+1<t''\leqslant t'$ since $w_{t''-1}\in N_{w_{t''}}$. Also clearly $\alpha(w_{t'})=3$. If $t+1<t''<t'$ then $w_{t''} = v_{s'}$ for some $j+1<s'<s$, and by minimality of $s$ the chord adjacent to $v_{s'}$ cannot have its other end in $W$. On the other hand, if this chord has its other end in $\{v_{s'+1},...,v_s\}$ then this would contradict minimality of $v_\ell,...,v_m$. $$\tag*{$\Box$}$$
I think the hypotheses of the proposition apply for all Honeycomb toroidal graphs; it's certainly true for $HTG(m,2n,\ell)$ when $\ell \leqslant m+2$, and I've also verified it under various arithmetic constraints on $(m,n,\ell)$. The strategy used in the proof also seems to work pretty well even for Hamiltonian cubic graphs that don't satisfy the other hypotheses, but the above hypotheses were the most general I could come up with that guarantee the process will succeed.
