Three-arc graphs: Characterization and domination

NEW

Problem: Interpret the question as asking for the optimal finite function

Here $X(G)$ is the 3-arc graph: its vertices are the arcs $uv$ of $G$, and $uv\sim xy$ in $X(G)$ iff $(v,u,x,y)$ is a 3-arc of $G$, equivalently $ux\in E(G)$, $v\ne x$, and $u\ne y$.

Result: No finite upper bound in terms of $\gamma(G)$ alone exists. In fact,

For $k=1$, take the wheel $W_n=K_1\vee C_n$, with center $c$ and rim vertices $r_0,\dots,r_{n-1}$. Then $W_n$ is connected, $\delta(W_n)=3$, and $\gamma(W_n)=1$.

Let $D$ be any dominating set of $X(W_n)$. For each $i$, consider the arc $r_i c$. If an arc $xy\in D$ dominates $r_i c$, then either $xy=r_i c$, or $xy\sim r_i c$. In the latter case, by the definition of $X(G)$,

is a 3-arc of $W_n$, so $x\in N(r_i)\setminus\{c\}=\{r_{i-1},r_{i+1}\}$. Hence, for every $i$, $D$ contains an arc whose tail is one of $r_{i-1},r_i,r_{i+1}$.

Thus the set of rim vertices appearing as tails of arcs in $D$ is a dominating set of the cycle $C_n$. Therefore

So

which is unbounded while $\gamma(W_n)=1$.

More generally, for fixed $k$, take $k$ wheels and join their centers in a path. The resulting graph is connected, has minimum degree at least $3$, has domination number exactly $k$, and still contains a wheel rim of arbitrarily large length, giving the same lower bound. Hence $F(k)=\infty$ for every $k\ge1$.

Therefore the requested sharp upper bound cannot be a finite function of $\gamma(G)$ alone.

Citation: No literature citation is needed for the counterexample above. The definition of $X(G)$ is the standard one used in Xu–Zhou, “Three-arc graphs: Characterization and domination.”