11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't quite understand the question. I guess you want $G$ to be a random graph on $n$ vertices, but from what probability model? Uniformly over all $2^{\binom{n}{2}}$ labeled graphs? Uniformly over unlabeled graphs (probably really hard)? Uniformly over (labeled or unlabeled) Hamiltonian graphs? Erdős–Rényi? Something else? (More formally, you have to specify a probability measure on the set of all graphs on $n$ vertices.) $\endgroup$ – Nate Eldredge Nov 20 '18 at 14:59
  • $\begingroup$ Also, I suppose your question is about the probability that every vertex of $G$ is of degree at least $n/2$. In which case you ought to write $P(G \in H_n \text{ and } \operatorname{deg}(v) \ge \frac{n}{2} \forall v \in G)\}$. But maybe you'd also be interested in the conditional probability $P( \operatorname{deg}(v) \ge \frac{n}{2} \forall v \in G \mid G \in H_n)$, which seems more along the lines of your question. $\endgroup$ – Nate Eldredge Nov 20 '18 at 15:02
  • $\begingroup$ @NateEldredge Reading over the entire question I agree now that it is unclear what probability I was interested in. I'm pretty sure I meant the conditional probability you mentioned (question updated now). I was considering the case of G being drawn uniformly from the set of non isomorphic hamiltonian graphs. However, just reading over your comments it is clear that I much more work to do in probability and graph theory before I can really investigate something like this! $\endgroup$ – 1730 Nov 20 '18 at 15:40
  • $\begingroup$ Why are p3 through p6 zero? There is at least one graph satisfying Dirac's condition. Gerhard "Probably It Is The Complement?" Paseman, 2018.11.20. $\endgroup$ – Gerhard Paseman Nov 20 '18 at 15:55
  • 3
    $\begingroup$ So, maybe you want to skip the probability language, and just say "What fraction of unlabeled Hamiltonian graphs on $n$ vertices satisfy the Dirac condition?" It's probably hopeless to get an exact closed-form answer, but you could hope for asymptotics. $\endgroup$ – Nate Eldredge Nov 20 '18 at 17:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.