0
$\begingroup$

I (will, at the end) have a connected, undirected graph with N nodes and 2N-3 edges. You can consider the graph as it is built onto an existing initial graph , which has 3 nodes and 3 edges, iteratively. Every node added onto the graph and has 2 connections with the existing nodes (not necessarily with the initial 3 only) in the graph. When all nodes are added to the graph (N-3 nodes added in total), the final graph is constructed.

I'm asked, what is the maximum number of nodes in this graph that can be visited exactly once (except for the initial node), i.e., what is the maximum number of nodes contained in the largest Hamiltonian path of the given graph. (Okay, saying largest Hamiltonian path is not a valid phrase, but considering the question's nature, I need to find a max. number of nodes that are visited once and the trip ends at the initial node. I thought it can be considered as a sub-graph which is Hamiltonian, and consists max. number of nodes, thus largest possible Hamiltonian path).

I tried to apply Ore's Theorem but even for a small example graph, the Ore's Theorem might not be sufficient to tell if the graph is Hamiltonian even though it strikes you directly that it is Hamiltonian.

I thought I might use BFS since It's used to detect cycles in a graph: I needed to find the largest cycle which contained all the nodes in that cycle but given a large number of nodes, this approach might be slow and not desirable in my case since the timing will be crucial. For now this option is the last option if I can't come up with a solution.

After some thinking, I thought whatever the number of nodes will be, the graph seems to be Hamiltonian due to node addition criteria. The problem is I can't be sure and I can't prove it. Does adding nodes in that fashion, i.e. adding new nodes with 2 edges which connect the added node to the existing nodes, alter the Hamiltonian property of the graph? If it doesn't alter the Hamiltonian property, how so? If it does alter, again, how so? Thanks.

EDIT

I, again, realized that building the graph the way I described might alter the Hamiltonian property. Consider an input given as follows:

1 3
2 3
1 5
1 3

these input says that 4th node is connected to node 1 and node 3, 5th to node 2 and node 3 . . .

4th and 7th node are connected to the same nodes, thus lowering the maximum number of nodes that can be visited exactly once, by 1. If i detect these collisions (including an input such as 3 3) and lower the maximum number of nodes, starting from N, I believe I can get the right result.

See, I do not choose the connections, they are given to me and I have to find the max. number of nodes.

I think counting the same connections while building the graph and subtracting it from N will give the right result? Can you confirm this or is there a flaw with this?

$\endgroup$
  • $\begingroup$ Your are searching for a largest cycle in a 2-tree with $N\geq 3$ vertices? $\endgroup$ – frafl Apr 6 '13 at 22:36
  • $\begingroup$ I'm exactly searching for the largest number of nodes, which satisfy the following: I will start from a node, traverse as much nodes as possible exactly once, and come back to where I started. I don't know it this fits what you described. $\endgroup$ – Varaquilex Apr 6 '13 at 22:42
  • $\begingroup$ @frafl I think you can also construct a 3-tree using that procedure, if when adding a new vertex you only choose two vertices that are adjacent as the neighborhood of the new vertex. $\endgroup$ – G. Bach Apr 6 '13 at 23:26
  • $\begingroup$ It is not clear if you choose the way to add the new edges at each step or an "enemy" chooses them. Could you please explain this? $\endgroup$ – fidbc Apr 7 '13 at 1:06
  • 3
    $\begingroup$ It does make a difference. Suppose the enemy chooses the edges and let 1,2,3 be the initial vertices. The enemy can choose to add vertices 4,...,n all of them adjacent to 1 and 2. Therefore the largest cycle/path would have length 4. If the edges are added randomly, its a completely different story. You might have to calculate the expected max length of a cycle/path. Finally, if you get to choose how to add the edges, then you can add them in such a way that the graph is planar and all vertices are in the unbounded face, therefore obtaining a Hamiltonian graph. $\endgroup$ – fidbc Apr 7 '13 at 3:21
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.