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.