Is it true that any hamilton graph with "k" vertices has k/2 as the maximum independent set?

Question

A Hamilton graph is a graph that has a Hamiltonian cycle ,which means a cycle exists in this graph in which you can visit every vertex of graph exactly once .

My observation is : - Say for a(any) Hamilton graph of 100 vertices , the value of its maximum independent set will be 50 .

Can somebody prove it or verify it ?

score 0 · Accepted Answer · answered Apr 06 '20 at 20:57

0

This is plainly false. The complete graph on $n>2$ vertices is Hamiltonian but has maximum independent set size of only $1$.

However, if a Hamiltonian graph on $2n$ vertices is bipartite, then it is true that its maximum independent set size is $n$ (take one bipartition).

answered Apr 06 '20 at 20:57

Parcly Taxel

103,344

maximum matching in a hamilton graph of "k" vertices is always (k+1)/2 , is this claim correct ?? – user768815 Apr 07 '20 at 04:50
@RiyaSingh Ask that as another question – Parcly Taxel Apr 07 '20 at 04:50
here it is : https://math.stackexchange.com/questions/3613511/maximum-matching-in-a-hamilton-graph-of-k-vertices-is-always-k1-2-is-this – user768815 Apr 07 '20 at 04:59
I have one more question : https://math.stackexchange.com/questions/3612906/maximum-matching-in-general-graph . – user768815 Apr 07 '20 at 05:00

Is it true that any hamilton graph with "k" vertices has k/2 as the maximum independent set?

1 Answers1