Skip to main content
2 of 8
added 1 character 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(G \in H_n \text{ and } \deg(v) \geq \frac{n}{2})$$

for $v\in G$. 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.

1729
  • 221
  • 1
  • 6