2
$\begingroup$

Come up with an example of graphs:

  • Graph $G$ without bridges and $G^2$ isn't Hamiltonian Graph.
  • Graph $G$ is triconnected graph, local-connected (it means that for all vertices: the environment of a vertex (without itself) is connected graph) and $G$ isn't Hamiltonian Graph
  • Graph $G$ is cubic graph, triconnected and $G$ isn't Hamiltonian Graph.
  • Graph $G$ is connected, local-Hamiltonian (it means that for all vertices: the environment of a vertex (without itself) is Hamiltonian Graph), and $G$ isn't Hamiltonian Graph.

Why:

  • If graph $G$ is connected, local-connected, edge-connected $\Rightarrow$ $G$ is Hamiltonian Graph.

Please give some examples or clues!

Thanks anyway!

  • 0
    @EuYu Maybe you know how to prove that $G^2$ from the first item from your offering isn't *Hamiltonian Graph*?2012-11-30

0 Answers 0