-2
$\begingroup$

Let $G=(V,E)$ be a connected simple undirected graph. A way in $G$ is a function $w:\{1,\ldots, n\}\to V(G)$ for some positive integer $n$, such that $\text{im}(w) = V(G)$, and for all $k\in \{1,\ldots, n-1\}$ we have $\{w(k), w(k+1)\} \in E$.

We define the hamiltonicity of $G$ by $$H(G) = \min\{n\in\mathbb{N}:\text{ there is a way } w:\{1, \ldots n\}\to V(G)\} - |V(G)|.$$

(A connected graph is Hamiltonian if and only if $H(G) = 0$.)

Is it true that for all connected graphs we have $H(G) \leq |V(G)| - 1$? Or can $H(G)$ become larger, even arbitrarily large with respect to $|V(G)|$?

Improve this question
$\endgroup$
5
  • $\begingroup$ What prevents a way to cover $V(G)$ multiple (arbitrarily many) times, like : $0\to 1 \to0\to 1 \to0\to 1 \to0\to 1 \to...$? $\endgroup$
    – Loïc Teyssier
    Commented May 1, 2017 at 7:24
  • 2
    $\begingroup$ "A [....] if and only if [...]" is false since you did not require your way to be closed, i.e., to have $w(1)=w(n+1)$, and since hamiltonian is most often taken to mean "has a Hamilton circuit". The standard term for has a Hamilton path is traceable. It will improve the question if you edit it to use standard terminology: your_ways_ would usually be called walk which visits every vertex at least once. And you should clarify whether you are intentionally only asking for Hamilton paths and not for Hamilton circuits.(Otherwise, add in a closedness-condition.) $\endgroup$
    – Peter Heinig
    Commented May 1, 2017 at 7:46
  • 4
    $\begingroup$ For readability, in a separate comment, the usual conventions nowadays are: alternating sequence of vertices and edges = walk, such a thing without edge-repetitions = trail, such a thing with neither edge- nor vertex-repetitions = path. $\endgroup$
    – Peter Heinig
    Commented May 1, 2017 at 7:49
  • $\begingroup$ Sorry, correction, you actually did require closedness. $\endgroup$
    – Peter Heinig
    Commented May 1, 2017 at 7:54
  • $\begingroup$ @PeterHeinig Where does he require closedness? $\endgroup$
    – bof
    Commented May 1, 2017 at 9:03

1 Answer 1

Reset to default
4
$\begingroup$

$H(G)\leq \lvert V(G)\rvert-1$ for every finite connected graph.

Proof. Consider any spanning tree $T$ of $G$, double every edge of $T$, choose any Euler tour $W$ of this auxiliary graph, consider the projection $\mathrm{p}(W)$ of $W$ to $G$. Then $\mathrm{p}(W)$ is a way in your sense having a domain of $2\lvert V(G)\rvert-1$ elements. After subtracting $\lvert V(G)\rvert$ we obtain the required upper bound of $\lvert V(G)\rvert-1$ on the "hamiltonicity" (in your sense).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .