The answer feels to be just a bit too obvious. I know it is true... but how do I prove it? Given two hamiltonian graphs \(G\) and \(H\), prove that \(G \times H\) is hamiltonian. I have thought of one method that will very likely take me nowhere. Take \(A \subset G \times H\) such that \(A\) is isomorphic to \(G\) or \(H\) and to note that all subgraphs \(A\) are hamiltonian. Then I kind of just fall apart there. I think it's because I have the wrong approach. This is the first question of my homework and so it should be the easiest... but I don't see it that way. I've proved all the other theorems that were supposed to be "harder." Hrm. How about this method? Assume \(G \times H\) is not hamiltonian, then prove that either \(G\) or \(H\) are not hamiltonian. I think I could prove this one by contradiction. Maybe something along the lines of taking the longest path or even the largest cycle (since we assumed to the contrary that \(G\) and \(H\) are hamiltonian). Thoughts? I think I am missing something obvious.
I think that you can do a brute-force proof along the lines of your first suggestion above. Suppose that \(H\) has \(n\) vertices, and that \(G\) has \(m\) vertices. Suppose we order the vertices in both \(G\) and \(H\) to correspond to Hamiltonian paths: \(\{h_1,h_2,\ldots,h_n\}\) where \(h_1\) is adjacent to \(h_n\), and likewise for \(G\). Suppose we start out at \(\{h_1,g_1\}\). Then, if \(n\) is even, follow a Hamiltonian path in \(G\), ending up at \(\{h_1,g_m\}\). Now, take one step along the Hamiltonian cycle in \(H\), putting us at \(\{h_2,g_m\}\) and follow the reverse path in \(G\) to get back to \(\{h_2,g_1\}\). Repeat this process until you get to the end. If \(n\) is even, you'll be at \(\{h_n,g_1\}\), which is adjacent to \(\{h_1,g_1\}\), and you're done. Note that you can interchange the roles of \(H\) and \(G\) in this approach, so it works as long as at least one of \(m\) and \(n\) are even. If both \(m\) and \(n\) are odd, start by using the same approach on the subgraph \(\{h_1,h_2,...,h_{n-1}\} \times \{g_1,g_2,...,g_{m-1}\}\), and omit the last step where you return to the starting. I.e., start at \(\{h_1,g_1\}\) and follow a Hamiltonian in \(G\) to \(\{h_1,g_{m-1}\}\), then step up to \(\{h_2,g_{m-1}\}\), follow the reverse Hamiltonian in \(G\) to end up at \(\{h_2,g_1\}\). Repeat until you end up at \(\{h_{n-1},g_1\}\). Now, step up to \(\{h_n,g_1\}\) and follow the Hamiltonian in \(G\) all the way to the end, putting you at \(\{h_n,g_m\}\). Finally, follow the reverse Hamiltonian in \(H\) to end up at \(\{h_1,g_m\}\), which is adjacent to \(\{h_1,g_1\}\). There's probably a slicker way to do it, and the notation could be clearer, but hopefully that answers your question. Also, I assumed you were talking about undirected graphs; was this warranted?
What do you mean by "order the vertices?" Yes, I am talking about undirected graphs. Thank you for your help. I think that asside from the one question that I have about it, I understand everything else. If you don't mind, I may post a proof that I did work out but I want to make sure my Logic is correct. Also, when you asked what I meant by \(\times\), is there another meaning to it in graph theory?
I mean we re-label the vertices, so that they are in the order they'd appear in (some) Hamiltonian cycle. This doesn't change the graph, just rearranges the order the vertices are listed in. This is just a convenience so that you can step through the vertices from 1 to n; it's not really necessary. There are a couple other graph products. For example, the categorical product, where a vertex is adjacent to another if each of its components is adjacent to each of the components of the other. As opposed to the Cartesian product, where you want one component equal and the other adjacent.
That's what I thought, I was just making sure. It's just that with math, I want to make sure we are 100% clear on meaning. Thank you Please Register or Log in to view the hidden image!
Just looking for a pointer here. Prove that if \(G\) is self-complementary and has order \(n\geq 5\), then \(G^{2}\) is hamiltonian-connected. I tried working the contradiction route (as I always try first) and assuming \(G^{2}\) is not hamiltonian-connected, then \(G\) contains a cut-vertex. Obviously, this takes me nowhere because if you look at \(n = 5\), there is a self-complementary graph that contains a cut vertex. What if I broke it into two cases.... Case 1: \(G\) is 2-connected. \(G\) is self-complementary and we assume to the contrary that \(G^{2}\) is not hamiltonian-connected. Then \(G\) contains a cut-vertex and this is a contradiction. Case 2: \(G\) contains a cut-vertex and is self-complementary. {insert whatever here} Case 2 seems to be the place where \(n \geq 5\) comes in because there is obviously a case in \(n = 5\) such that it is self-complementary and contains a cut-vertex. \(n = 4\) doesn't work just by a simple trial. So I wonder... what is so special about \(n = 5\) and greater? I'm just looking for a pointer in the right direction and not the answer.
Well, \(n=5\) is the minimum for self-complementary graphs to be interesting. The only self-complementary graphs with lower order are the trivial \(n=1\) case and the almost-trivial path graph with \(n=4\). There just aren't enough degrees of freedom to allow interesting self-complementary graphs with less than 5 vertices. That's not a very deep answer, but hopefully it jogs your thinking... As far as the proof goes, I'd try to use the diameter property of self-complementary graphs. That is, all self-complementary graphs have diameter of either 2 or 3. I.e., you can step from any vertex to any other with at most 2 or 3 steps. So, if the diameter of some graph \(G\) is 2, it follows that \(G^2\) is completely connected, and so trivially Hamiltonian. For the case when the diameter is 3, you can show that \(G\) must be 2-connected (from which it follows that \(G^2\) is Hamiltonian). To see this, suppose that \(G\) is a self-complementary graph of diameter 3 that contains some vertex with only one edge. Then, this same vertex is connected to all but one of the vertices in the complement of \(G\). This implies that there is some vertex in \(G\) which is also connected to all but one vertex, implying that the diameter of \(G\) must be 2, which contradicts the assumptions.
Are you showing that it's hamiltonian or hamiltonian-connected? The latter implies the former, but not that other way around.
When I say "Hamiltonian," I mean that there exists a Hamiltonian cycle. As I understand it, that's actually stronger than Hamiltonian-connected. It seems that you're using Hamiltonian in a weaker sense, which is to say that there exists a Hamiltonian path? The term I'm familiar with for that type of graph is "traceable." Does your book/source use different terminology than this? I'm happy to adopt whatever terminology you're working with, if you'll clarify what the various definitions are. But now that I think about it, the fact that the proof only asks for Hamilton-connected instead of Hamiltonian (in the cyclical sense) may be significant... Also, there's an error in my proof. I showed that there cannot be a "hanging" vertex in a self-complementary graph of diameter 3, but it is still possible to have graphs without hanging vertices that are not 2-connected. So, we either need to strengthen the proof to handle those cases or scrap the approach of showing that \(G\) is 2-connected altogether... How about this: suppose \(G\) is a self-complementary graph of diameter 3 that contains a cut-vertex, call it \(v_c\). Then, \(G\) contains two subgraphs, \(G_1\) and \(G_2\) that are connected only through \(v_c\). Then, in the complement of \(G\), every vertex in \(G_1\) is connected to every vertex in \(G_2\), and at least one vertex in each subgraph is connected to \(v_c\). This implies that the diameter of the complement of \(G\) must be 2, which contradicts the assumptions. Therefore, all self-complementary graphs of diameter 3 are biconnected, implying that their second powers contain Hamiltonian cycles.
Saying that a graph G is hamiltonian connect graph is stronger than saying it contains a hamiltonian cycle. A hamiltonian-connected graph is one such that for all u and v in the vertex set (u != v), there exists a hamiltonian u-v path. So, the cycle graph \(C_{5}\) is hamiltonian, but it is not hamiltonian-connected. If you label the cycle as \(v_{1}v_{2}v_{3}v_{4}v_{5}v_{1}\), you see there is no hamiltonian path between \(v_{1}\) and \(v_{3}\) because you cannot include all vertices (take the longest path and you see that we cannot include \(v_{2}\))
Oh, I get it. I had the silly idea that Hamiltonian-connected meant that you could start a Hamiltonian path at any vertex... Anyway, I think my approach still works for your case 2, right? I.e., if the graph is self-complementary and contains a cut-vertex, it must have diameter 2, in which case its square is completely connected, and so trivially Hamiltonian-connected. For case 1 you use the result that if \(G^2\) is not Hamiltonian-connected, \(G\) must contain a cut-vertex. Or, equivalently, if \(G\) is biconnected (and self-complementary?), \(G^2\) is Hamiltonian-connected. Do you have a proof for this?
I got something different... when you look at it's complement.... ------------------ Let \(G\) be a self-complementary graph containing a cut-vertex \(v\). Then \(diam(G) = 3\) Proof: Assume to the contrary that \(diam(G) = 2\). It follows that all vertices in \(G\) must be adjacent to \(v\), otherwise there would exist a minimal path longer than \(diam(G) = 2\) and this contradicts the assumption. In \(\overline{G}\), we see that no vertex is adjacent to \(v\) and \(\overline{G}\) is disconnected. Hence, \(G\) is not self-complementary and this is a contradiction. ------------------- This is correct? If this is, I will need to figure out how \(diam(G) = 3\) implies that \(G^{2}\) is hamiltonian-connected. What a bitch of a problem... I had to pull outside sources to get an idea on how to do this... but then again, I have never done problems like this before Please Register or Log in to view the hidden image! Please Register or Log in to view the hidden image! And you see the first n = 5 graph has \(diam(G) = 3\), yet it is not biconnected.
Yeah, there are some oversights in my proof; your derivation is correct. A couple more ideas: \(G^2\) will have diameter 2 in this case. You should also be able to show that it doesn't contain any cut-vertices (i.e., if \(G\) was biconnected, the square should certainly be, and if \(G\) contained a cut-vertex, it gets swamped out in the square). Is there a sufficient condition for a graph to be Hamiltonian-connected?
Well I had to turn in the problem... unfinished. However, as I turned it in I had what I think is the idea that would finally solve the problem. Would it possible for \(G^{2}\) to be panconnected given that \(G\) is separable, \(diam(G) = 3\), and \(G\) is self-complementary? I'll say more about it later... right now I need to worry about getting off campus to get home.
It turns out that no one in my graph theory class even solved this problem. Even the graduate students had trouble. Monday we may get an answer to this proof (as the professor usually goes over homework). When he does, I'll be sure to post the proof he gave. I am betting it goes along the lines of what we worked on. My question is... as I conjectured above... Would it possible for \(G^{2}\) to be panconnected given that \(G\) is separable, \(diam(G) = 3\), and \(G\) is self-complementary? I thank you for your help Please Register or Log in to view the hidden image!
In the movie "Good Will Hunting," the class was asked to prove a "hard theorem" that was on the chalk board. One of the questions was that for a given graph \(G\), find the generating function for the walk \(i \rightarrow j\). My question is... what does this mean? The letters \(i\) and \(j\) refer to any two vertices in \(G\). Note: if you look at the actual "theorem," it wasn't even a theorem.. just a set of problems that anyone taking an introductory graph theory course could solve in 2 minutes.
