We consider only finite, simple, undirected graphs here. An orientation of a graph $G$ is obtained by assigning some direction to each edge of $G$.

(Question starts)
A graph is locally linear if every edge is in exactly one triangle. Let $G$ be a connected locally linear 4-regular graph with an orientation $\overrightarrow{G}$ which orients every triangle $(u,v,w)$ in $G$ cyclically (i.e., either $u\to v\to w$ or $v\to u\to w$).
[Side note: $\overrightarrow{G}$ is an Eulerian orientation in the sense that every vertex has two in-coming edges and two out-going edges.]
A direction alternating cycle in $\overrightarrow{G}$ is a cycle $(v_1,v_2,\dots,v_k)$ such that direction of adjacent edges alternate (that is, either $v_1\to v_2\leftarrow v_3\to v_4\leftarrow \dots v_k\leftarrow v_1$ or $v_1\leftarrow v_2\to v_3\leftarrow v_4\to \dots v_k\to v_1$). Note that in a direction alternating cycle in $\overrightarrow{G}$, adjacent edges in the cycle belong to different triangles in $G$ (becuase triangles are oriented cyclically); that is for each direction alternating cycle $D_i$ in $G$, $G[V(D_i)]$ is trianngle-free. Clearly, $\overrightarrow{G}$ can be (edge) decomposed into direction alternating cycles.

Problem 1: Characterize orientations $\overrightarrow{G}$ that admit a cycle decomposition into exactly four direction alternating cycles.

Since a complete characterization may be challenging, let us consider necessary/sufficient conditions.
It seems that $G$ should be 4-connected (there exist graphs $G$ with vertex connectivity 3 such that some orientation $\overrightarrow{G}$ of $G$ does not decompose into four direction alternating cycles).
For a concrete special case, assume that $G$ is also 4-connected and planar, and $\overrightarrow{G}$ orients every face boundary cyclically.
Problem 2: Can we say that $\overrightarrow{G}$ admits a cycle decomposition into exactly four direction alternating cycles?

It seems that line graph of $CL_{4q}$ has such a decomposition. $CL_{4q}$ is the circular ladder graph such that inner and outer cycles are the cycle $C_{4q}$; e.g.: $CL_4$ is the cube (also called 3-cube). Such decompositions of $L(CL_4)$ and $L(CL_8)$ are given below (all intersection points are vertices, and the four cycles are given distinct colours). enter image description here
Cycle decompositions $D=\{D_1,D_2,\dots,D_t\}$ of $G$ such that $G[V(D_i)]$ is triangle-free for $1\leq i\leq t$ are in one-to-one correspondence with cycle double covers of clique graph $K(G)$ of $G$ (it is known that $G$ will be a cubic graph and line of graph of $K(G)$ will be $G$).

PS: Unfortunately, graphclasses.org does not include the class locally linear. Any reference that deal with decompositions of locally linear graphs is welcome; hence the tag reference-request. Of course, such graphs admit a triangle decomposition, a $P_3$-decomposition, and a $P_4$-decomposition (the last one is because #edges is a multiple of three).


Your Answer

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

Browse other questions tagged or ask your own question.