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
    By the *environment* of $v$ you mean the subgraph generated by the neighbors of $v$?2012-11-30
  • 0
    The first one seems impossible. The square of any biconnected graph is Hamiltonian.2012-11-30
  • 1
    Some thoughts: **1.** seems impossible. See [here](http://www.sciencedirect.com/science/article/pii/0095895674900914) **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](http://www.sciencedirect.com/science/article/pii/S0167506008700797) 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?2012-11-30
  • 0
    @BrianM.Scott Yep2012-11-30
  • 0
    @EuYu Can you see the picture for "On Minimal Non-Hamiltonian Locally Hamiltonian Graphs"?2012-11-30
  • 0
    Nope, I can't access the article. A bit ironic since the article seems to originate from my university.2012-11-30
  • 0
    @EuYu About the first item: Graph $G$ without bridges (can have points of articulation) and bi-connected graph (can not have points of articulation) it is different definitions.2012-11-30
  • 1
    @jofisher Oh of course. Silly mistake on my part.2012-11-30
  • 0
    @jofisher Allow me to reprimand my mistake by offering [this](http://mathoverflow.net/questions/50355/wanted-a-graph-g-without-bridges-whose-square-is-not-hamiltonian).2012-11-30
  • 0
    @EuYu What is the offering? :)2012-11-30
  • 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.2012-11-30
  • 0
    @EuYu Big example :) Nice link! It's pitty that I have no acces to example for 2 and 4 item. But thanks anyway!2012-11-30
  • 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