1
$\begingroup$

(Preface)
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).

$\endgroup$
0

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.