Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hamiltonicity]

For questions related to the Hamiltonicity of a graph.

1
vote
1answer
28 views

Every cubic 3-connected Hamiltonain graph has three Hamiltonian cycles with special property

It is known that every cubic Hamiltonian graph has at least three Hamiltonian cycles (by Tutte's theorem that every edge of a cubic graph belongs to an even number of Hamiltonian cycles) It is true ...
2
votes
0answers
69 views

With reference to the Lifting of Hamiltonian cycles

Can someone please help to understand about the concept of "lifting Hamiltonian cycles (in Cayley graphs)"? As an example how the existence of a Hamiltonian cycle is shown by using the concept of ...
2
votes
0answers
41 views

Question regarding the factor group lemma for Cayley graphs

Can someone please explain the proof of the "Factor group lemma" for Cayley graphs which is stated below. Factor Group Lemma: Suppose that 1.$N$ is a cyclic, normal subgroup of a group $G$. 2.$(s_1,...
1
vote
1answer
21 views

Hamiltonian decomposability of 4- regular graphs

If a 4 regular graph is hamiltonian can we say it is hamiltonian decomposable ? Thanks a lot in advance
0
votes
0answers
10 views

Pseudo hamiltonian connected property of a graph

Is there a connection between pseudo hamiltonian connectedness and hamiltonicity of graphs?
2
votes
0answers
78 views

Doubt on the definition of closure of a graph.

The closure of a graph $G$, denoted $cl(G)$ is defined to be the supergraph of $G$ obtained from $G$ by recursively joining pairs of nonadjecent vertices whose degree sum is atleast $n$ untill no ...
0
votes
0answers
28 views

Question regarding factor group lemma

Factor Group Lemma: Suppose that 1.$N$ is a cyclic, normal subgroup of group $G$. 2.$(s_1,s_2,\ldots,s_m)$ is a hamiltonian cycle in $Cay(G/N;S)$. 3.The product $s_1s_2\cdots s_m$ generates $N$. ...
3
votes
1answer
87 views

If every $H$-free $2$-connected graph is Hamiltonian then $H$ is $P_3$

I'm stuck with exercise 5 page 72 of Harris, Hirst and Mossinghoff's Combinatorics and Graph Theory: Show that if being $H$-free implies Hamiltonicity in $2$-connected graphs (where $H$ is ...