Questions tagged [hamiltonian-path]

A path in a graph that visits each vertex exactly once.

128 questions
191 views

Show that the line graph of any quasi-cyclic graph contains a Hamiltonian cycle.

The definition I have been given for a quasi-cyclic graph is as follows: a graph $G=(V, E)$ is quasi-cyclic if $1)$ it contains a unique cycle $C=(V(C), E(C))$ and $2)$ for each edge $xy$ in $E$ at ...
46 views

Hamiltonian circuits / graphing

Can someone tell me if I'm correctly doing these graphs for Hamiltonian circuits? I know that you start at the root node and show the path "back" in a tree. But what if it crosses and such. I'm just ...
626 views

Hamiltonian path in a complement of a tree

T is a tree on n-vertices for which the greatest degree is smaller than n-1, prove that the complement of T has a Hamiltonian path. I was trying to achieve Ore's inequality, this is what I have ...
61 views

Number of Hamiltonian Cycles in planar chordal graph

I have a given planar chordal graph $G$. Due to the construction of $G$ I know that there exists at least one Hamiltonian cycle in $G$. My question is: How many Hamiltonian cycles are in $G$? (an ...
32 views

bulding a Hamilton circuit in a given graph

Let G be an undirected graph with k components. assume that every components consist a Hamilton circuit. prove that by adding exactly k edges to the graph you can achieve a connected graph with ...
126 views

How many Hamiltonian cycles are there in $K_{10,10}$?

I want to calculate the number of Hamiltonian cycles in $K_{10,10}.$ Could anyone help me? I think in $K_{10}$ we have $9!$ Hamiltonian cycles.
491 views

Examples of non-hamiltonian decomposable graphs

Good Afternoon! I read that Line graph of the Petersen graph is 4-regular 4-edge-connected and non-hamiltonian decomposable. Does someone knows examples (or references) of non-hamiltonian ...
198 views

when are Kneser graphs connected?

For the kneser graphs $K(n,k)$. The vertices of $K(n, k)$ are all $k-$subsets of the set $\{1, 2 ,......,n \}$ and two vertices are adjacent to each other if and only if the $k-$subsets are ...