Two Sufficient Conditions for P_3-dominated Hamiltonian Graphs

NEW

Problem: Reconstructed statement: for every finite simple graph $G$ with $|V(G)|\ge 3$, if $G$ is triangularly connected and $P_3$-dominated, then $G$ is vertex pancyclic, except for $K_{1,1,3}$. Here triangularly connected means every two edges are joined by a chain of triangles sharing edges consecutively; $P_3$-dominated means every copy of $P_3$ is a dominating subgraph; vertex pancyclic means every vertex lies on a cycle of every length $3,\dots, |V(G)|$.

Result: The conjecture is false. In fact, the whole family $K_{1,1,m}$ for $m\ge 3$ gives counterexamples, so $K_{1,1,4}$ is already a counterexample not covered by the stated exception.

Let

with partite sets $\{a\},\{b\},X=\{x_1,x_2,x_3,x_4\}$. Thus $a$ and $b$ are adjacent, each $x_i$ is adjacent to both $a$ and $b$, and there are no edges among the $x_i$.

First, $G$ is triangularly connected. Every edge lies in a triangle: edge $ab$ lies in $abx_i$, and edge $ax_i$ or $bx_i$ lies in triangle $abx_i$. Moreover all these triangles share the common edge $ab$, so any two edges are connected by a chain of edge-overlapping triangles.

Second, $G$ is $P_3$-dominated. Any path on three vertices contains at least one of $a,b$, and in fact the vertex set of the path dominates all of $G$: every $x_j\notin V(P)$ is adjacent to $a$ or $b$, and $a,b$ are adjacent to all vertices outside themselves. Hence every $P_3$ is a dominating subgraph.

But $G$ is not vertex pancyclic. More strongly, $G$ has no cycle of length $5$ or $6$. Since $X$ is independent, no two vertices of $X$ can be consecutive on a cycle. Therefore a cycle can contain at most two vertices of $X$, because only the two vertices $a,b$ are available to separate them. Hence every cycle has length at most $4$. Since $|V(G)|=6$, $G$ is not Hamiltonian and therefore not vertex pancyclic.

Thus $K_{1,1,4}$ satisfies all stated hypotheses, is not isomorphic to the listed exception $K_{1,1,3}$, and fails the conclusion.

Citation: No external citation is needed; the counterexample is explicit.