Skip to main content
5 of 8
deleted 7 characters in body
1729
  • 221
  • 1
  • 6

Quantitatively characterizing the failure of the converse of Dirac's theorem

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.

1729
  • 221
  • 1
  • 6