2 added 26 characters in body
source | link

Let $k_P$ and $k_C$ be the maximum length of a Hamiltonian path and cycle, respectively, in the resulting graph $G$ (with $n$ vertices, $n\geq 5$). If the input is given to you, then $4\leq k_P\leq n-1$ and $4\leq k_C\leq n$.

The lower bound can be achieved when vertices $4,\ldots,n$ are all joined to vertices $1$ and $3$. In this case $C=1234$$C=(1,2,3,4)$ and $P=21435$$P=(2,1,4,3,5)$ are longest cycle and path, respectively.

The upper bound can be achieved when vertex $i$ is joined to vertices $i-1$ and $i-2$, $4\leq i\leq n$. In this case you get an outerplanar 2-connected graph, which is Hamiltonian, so $k_P=n-1$ and $k_C=n$.

Not sure how to find $k_P$ and $k_C$ in general since, during the construction, the property that the graph is Hamiltonian (and therefore the length of the longest path/cycle) is changing depending on how edges are added.

Let $k_P$ and $k_C$ be the maximum length of a path and cycle respectively in the resulting graph $G$ (with $n$ vertices, $n\geq 5$). If the input is given to you, then $4\leq k_P\leq n-1$ and $4\leq k_C\leq n$.

The lower bound can be achieved when vertices $4,\ldots,n$ are all joined to vertices $1$ and $3$. In this case $C=1234$ and $P=21435$ are longest cycle and path respectively.

The upper bound can be achieved when vertex $i$ is joined to vertices $i-1$ and $i-2$, $4\leq i\leq n$. In this case you get an outerplanar 2-connected graph, which is Hamiltonian, so $k_P=n-1$ and $k_C=n$.

Not sure how to find $k_P$ and $k_C$ in general since, during the construction, the property that the graph is Hamiltonian (and therefore the length of the longest path/cycle) is changing depending on how edges are added.

Let $k_P$ and $k_C$ be the maximum length of a Hamiltonian path and cycle, respectively, in the resulting graph $G$ (with $n$ vertices, $n\geq 5$). If the input is given to you, then $4\leq k_P\leq n-1$ and $4\leq k_C\leq n$.

The lower bound can be achieved when vertices $4,\ldots,n$ are all joined to vertices $1$ and $3$. In this case $C=(1,2,3,4)$ and $P=(2,1,4,3,5)$ are longest cycle and path, respectively.

The upper bound can be achieved when vertex $i$ is joined to vertices $i-1$ and $i-2$, $4\leq i\leq n$. In this case you get an outerplanar 2-connected graph, which is Hamiltonian, so $k_P=n-1$ and $k_C=n$.

Not sure how to find $k_P$ and $k_C$ in general since, during the construction, the property that the graph is Hamiltonian (and therefore the length of the longest path/cycle) is changing depending on how edges are added.

1
source | link

Let $k_P$ and $k_C$ be the maximum length of a path and cycle respectively in the resulting graph $G$ (with $n$ vertices, $n\geq 5$). If the input is given to you, then $4\leq k_P\leq n-1$ and $4\leq k_C\leq n$.

The lower bound can be achieved when vertices $4,\ldots,n$ are all joined to vertices $1$ and $3$. In this case $C=1234$ and $P=21435$ are longest cycle and path respectively.

The upper bound can be achieved when vertex $i$ is joined to vertices $i-1$ and $i-2$, $4\leq i\leq n$. In this case you get an outerplanar 2-connected graph, which is Hamiltonian, so $k_P=n-1$ and $k_C=n$.

Not sure how to find $k_P$ and $k_C$ in general since, during the construction, the property that the graph is Hamiltonian (and therefore the length of the longest path/cycle) is changing depending on how edges are added.