Return to Question

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.

I am currently in a combinatorics and graph theory class and recently we have been studying Hamiltonian graphs. We have been discussing a few theorems characterizing these graphs. I am interested in Dirac's theorem which states

Dirac (1952) Let $G$ be a simple graph with $n \geq 3$ vertices such that for any vertex $v \in G$ we have $\deg(v) \geq \frac{n}{2}$. Then $G$ is Hamiltonian.

The converse is easily seen to be false. I am interested in understanding how often the converse fails. From my view, one way to make this precise is as follows. Let $H_n$ denote the set of Hamiltonian graphs on $n$-vertices. What can we say about the probability $$p_n = P(\deg(v) \geq \frac{n}{2},\forall v\in G \mid G \in H_n)$$

I am mainly interested in what happens as $n \to \infty$. For example, I think it might be interesting if Dirac's theorem becomes necessary and sufficient if we take $n$ large enough. One could also investigate analogous question for other theorems that give sufficient conditions for $G$ to be Hamiltonian (Ore's theorem, Posa's theorem). However, Dirac's seemed the simplest to investigate.

Is there any literature on questions resembling this?

Thanks.

Edit:

I have fixed my maple code and believe I now have the correct probabilities for $n=3,4,5,6,7,8,9$ computed:

• $p_3 = 1$
• $p_4 = 1$
• $p_5 = \frac{3}{8} = 0.375$
• $p_6 = \frac{19}{48} \approx 0.396$
• $p_7 = \frac{29}{383} \approx 0.075$
• $p_8 = \frac{106}{1549} \approx 0.068$
• $p_9 = \frac{1165}{177083} \approx 0.007$

So maybe $p_n \to 0$ as $n \to \infty$? Of course this is clearly not enough data to make any reasonable conjectures. Much more powerful computers than mine would likely be needed. Thanks everyone for the useful comments, I imagine this question could probably be closed.

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.

I am currently in a combinatorics and graph theory class and recently we have been studying Hamiltonian graphs. We have been discussing a few theorems characterizing these graphs. I am interested in Dirac's theorem which states

Dirac (1952) Let $G$ be a simple graph with $n \geq 3$ vertices such that for any vertex $v \in G$ we have $\deg(v) \geq \frac{n}{2}$. Then $G$ is Hamiltonian.

The converse is easily seen to be false. I am interested in understanding how often the converse fails. From my view, one way to make this precise is as follows. Let $H_n$ denote the set of Hamiltonian graphs on $n$-vertices. What can we say about the probability $$p_n = P(\deg(v) \geq \frac{n}{2},\forall v\in G \mid G \in H_n)$$

I am mainly interested in what happens as $n \to \infty$. For example, I think it might be interesting if Dirac's theorem becomes necessary and sufficient if we take $n$ large enough. One could also investigate analogous question for other theorems that give sufficient conditions for $G$ to be Hamiltonian (Ore's theorem, Posa's theorem). However, Dirac's seemed the simplest to investigate.

Is there any literature on questions resembling this?

Thanks.

Edit:

I have fixed my maple code and believe I now have the correct probabilities for $n=3,4,5,6,7,8,9$ computed:

• $p_3 = 1$
• $p_4 = 1$
• $p_5 = \frac{3}{8} = 0.375$
• $p_6 = \frac{19}{48} \approx 0.396$
• $p_7 = \frac{29}{383} \approx 0.075$
• $p_8 = \frac{106}{1549} \approx 0.068$
• $p_9 = \frac{1165}{177083} \approx 0.007$

So maybe $p_n \to 0$ as $n \to \infty$? Of course this is clearly not enough data to make any reasonable conjectures. Much more powerful computers than mine would likely be needed. Thanks everyone for the useful comments, I imagine this question could probably be closed.

Edit: One final comment, I think that regular graphs could be an important tool. Since it is clear that for a $k$-regular graph $G$ on $n$ vertices if $n$ is taken large enough then $G$ cannot satisfy Dirac's condition. Thus if one could show the existance of a subset of k-regular graphs $R_k \subset H_n$ that grows large as $n \to \infty$ this might force the set of graphs satisfying Dirac's condition to become small. This paper might be useful although I'm not familiar with applying analysis and probability to graph theory so I only have a cursory understanding of it.

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.

I am currently in a combinatorics and graph theory class and recently we have been studying Hamiltonian graphs. We have been discussing a few theorems characterizing these graphs. I am interested in Dirac's theorem which states

Dirac (1952) Let $G$ be a simple graph with $n \geq 3$ vertices such that for any vertex $v \in G$ we have $\deg(v) \geq \frac{n}{2}$. Then $G$ is Hamiltonian.

The converse is easily seen to be false. I am interested in understanding how often the converse fails. From my view, one way to make this precise is as follows. Let $H_n$ denote the set of Hamiltonian graphs on $n$-vertices. What can we say about the probability $$p_n = P(\deg(v) \geq \frac{n}{2},\forall v\in G \mid G \in H_n)$$

I am mainly interested in what happens as $n \to \infty$. For example, I think it might be interesting if Dirac's theorem becomes necessary and sufficient if we take $n$ large enough. One could also investigate analogous question for other theorems that give sufficient conditions for $G$ to be Hamiltonian (Ore's theorem, Posa's theorem). However, Dirac's seemed the simplest to investigate.

Is there any literature on questions resembling this?

Thanks.

Edit:

The previous calculations for various $p_n$ values were clearly wrong and have been removed.

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.

I am currently in a combinatorics and graph theory class and recently we have been studying Hamiltonian graphs. We have been discussing a few theorems characterizing these graphs. I am interested in Dirac's theorem which states

Dirac (1952) Let $G$ be a simple graph with $n \geq 3$ vertices such that for any vertex $v \in G$ we have $\deg(v) \geq \frac{n}{2}$. Then $G$ is Hamiltonian.

The converse is easily seen to be false. I am interested in understanding how often the converse fails. From my view, one way to make this precise is as follows. Let $H_n$ denote the set of Hamiltonian graphs on $n$-vertices. What can we say about the probability $$p_n = P(\deg(v) \geq \frac{n}{2},\forall v\in G \mid G \in H_n)$$

I am mainly interested in what happens as $n \to \infty$. For example, I think it might be interesting if Dirac's theorem becomes necessary and sufficient if we take $n$ large enough. One could also investigate analogous question for other theorems that give sufficient conditions for $G$ to be Hamiltonian (Ore's theorem, Posa's theorem). However, Dirac's seemed the simplest to investigate.

Is there any literature on questions resembling this?

Thanks.

Edit:

I have fixed my maple code and believe I now have the correct probabilities for $n=3,4,5,6,7,8,9$ computed:

• $p_3 = 1$
• $p_4 = 1$
• $p_5 = \frac{3}{8} = 0.375$
• $p_6 = \frac{19}{48} \approx 0.396$
• $p_7 = \frac{29}{383} \approx 0.075$
• $p_8 = \frac{106}{1549} \approx 0.068$
• $p_9 = \frac{1165}{177083} \approx 0.007$

So maybe $p_n \to 0$ as $n \to \infty$? Of course this is clearly not enough data to make any reasonable conjectures. Much more powerful computers than mine would likely be needed. Thanks everyone for the useful comments, I imagine this question could probably be closed.

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.

I am currently in a combinatorics and graph theory class and recently we have been studying Hamiltonian graphs. We have been discussing a few theorems characterizing these graphs. I am interested in Dirac's theorem which states

Dirac (1952) Let $G$ be a simple graph with $n \geq 3$ vertices such that for any vertex $v \in G$ we have $\deg(v) \geq \frac{n}{2}$. Then $G$ is Hamiltonian.

The converse is easily seen to be false. I am interested in understanding how often the converse fails. From my view, one way to make this precise is as follows. Let $H_n$ denote the set of Hamiltonian graphs on $n$-vertices. What can we say about the probability $$p_n = P(\deg(v) \geq \frac{n}{2},\forall v\in G \mid G \in H_n)$$

I am mainly interested in what happens as $n \to \infty$. For example, I think it might be interesting if Dirac's theorem becomes necessary and sufficient if we take $n$ large enough. I have done a few computations in Maple and found that $p_n = 0 $ for $n=3,4,5,6$ and $p_7=0.075,p_8=0.144$ (I am currently calculating $p_9$ but doubt it will be anything suprising). One could also investigate analogous question for other theorems that give sufficient conditions for $G$ to be Hamiltonian (Ore's theorem, Posa's theorem). However, Dirac's seemed the simplest to investigate.

Is there any literature on questions resembling this?

Thanks.

Final Edit:

Ok I calculated $p_9$ ($p_{10}$ seems hopeless on my computer). In summary the probabilities are as follows:

• $p_2 = NaN$
• $p_3 = 0$
• $p_4 = 0$
• $p_5 = 0$
• $p_6 = 0$
• $p_7 = \frac{29}{383} \approx 0.075$ (29 Hamiltonian graphs satisfying Dirac's condition)
• $p_8 = \frac{28}{1549} \approx 0.018$ (112 Hamiltonian graphs satisfying Dirac's condition)
• $p_9 = \frac{13858}{177083} \approx 0.078$ (13858 Hamiltonian graphs satisfying Dirac's condition).

Strangely this $p_8$ is different from the first time I ran the program. But I have ran the program several more times and this seems to be the correct one.

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.

I am currently in a combinatorics and graph theory class and recently we have been studying Hamiltonian graphs. We have been discussing a few theorems characterizing these graphs. I am interested in Dirac's theorem which states

Dirac (1952) Let $G$ be a simple graph with $n \geq 3$ vertices such that for any vertex $v \in G$ we have $\deg(v) \geq \frac{n}{2}$. Then $G$ is Hamiltonian.

The converse is easily seen to be false. I am interested in understanding how often the converse fails. From my view, one way to make this precise is as follows. Let $H_n$ denote the set of Hamiltonian graphs on $n$-vertices. What can we say about the probability $$p_n = P(\deg(v) \geq \frac{n}{2},\forall v\in G \mid G \in H_n)$$

I am mainly interested in what happens as $n \to \infty$. For example, I think it might be interesting if Dirac's theorem becomes necessary and sufficient if we take $n$ large enough. One could also investigate analogous question for other theorems that give sufficient conditions for $G$ to be Hamiltonian (Ore's theorem, Posa's theorem). However, Dirac's seemed the simplest to investigate.

Is there any literature on questions resembling this?

Thanks.

Edit:

The previous calculations for various $p_n$ values were clearly wrong and have been removed.