Determine all connected graph $G$ such that subdivision graph $S(G)$ is Hamiltonian

565 Views Asked by At

Determine all connected graph $G$ such that subdivision graph $S(G)$ is Hamiltonian

The subdivision graph $S(G)$ of a graph $G$ is that graph obtained from $G$ by replacing each edge $e=uv$ of $G$ by a new vertex $w_e$ and 2 new edges $uw_e$ and $vw_e$

Let $S(G)$ be the subdivision graph of $G$ such that $|S(G)|=n$. Let $u\in V(G)$ and $w\in S(G)$, but $w\not \in V(G)$. In order for $S(G)$ to be Hamiltonian, $$ \deg(u) \geq \frac{n}{2} $$ and $$ \deg(w) \geq \frac{n}{2}. $$ I think that if $G$ is an Hamiltonian can be a candidate, but Hamiltonian is just a cycle that cover all the vertices, if there is one edge of $G$ not in the Hamiltonian cycle, then $S(G)$ will not be Hamiltonian.

1

There are 1 best solutions below

0
On BEST ANSWER

If $S(G)$ is an hamiltonian graph, then there exist a cicle that pass through every nodes, but if $w_e$ is a new node, then it must pass from the edges $uw_e$ and $w_ev$.

This means that on $G$, the same cycle is an eulerian cycle that don't pass throught the same node more than once.
But it is possible only if every node has degree $2$, so the only connected $G$ with such property are the cycles $C_n$