Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
By the environment of $v$ you mean the subgraph generated by the neighbors of $v$? –  Brian M. Scott Nov 30 '12 at 1:13
    
The first one seems impossible. The square of any biconnected graph is Hamiltonian. –  EuYu Nov 30 '12 at 1:21
1  
Some thoughts: 1. seems impossible. See here 3. is given by the Petersen graph. 4. Every locally Hamiltonian graph is $3$-connected and locally connected so an example here will also suffice for 2. This reference suggests that the smallest example for will be of order $11$. "If graph $G$ is connected, local-connected, ..." I don't understand why you think the result is true, doesn't 2 and 4 both provide counter-examples to it? –  EuYu Nov 30 '12 at 3:07
1  
@jofisher Oh of course. Silly mistake on my part. –  EuYu Nov 30 '12 at 5:46
1  
The link is to a question on Overflow. The answer provides a link to a paper which contains a bridgeless graph whose square is non-Hamiltonian. You can view the graph by following the links and previewing the article. –  EuYu Nov 30 '12 at 6:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.