Означает ли

Обозначим через минимальную степень выхода в G , а через δ - ( G ) минимальную степень.$\delta^+(G)$$G$$\delta^-(G)$

В связанном вопросе я упомянул расширение Гуила-Хури теоремы Дирака о гамильтоновых циклах , которое предполагает, что если тогда G гамильтоново.$\delta^+(G),\delta^-(G) \geq \frac{n}{2}$

В своем комментарии Саид прокомментировал другое расширение, которое кажется более сильным, за исключением того, что оно требует сильной связи графа.

Сильная связность оказалась доказанной избыточностью для теоремы Гуила-Хоури примерно через 30 лет после ее первой публикации, и мне было интересно, верно ли то же самое для расширения, представленного Саидом.

Итак, вопрос:

1. Кто доказал (может ли кто-нибудь найти ссылку), что означает, что G является гамильтоновым, учитывая, что G сильно связна?$\delta^+(G)+\delta^-(G) \geq n$$G$$G$

2. Является ли сильная связность избыточной и здесь, т. Е. Означает ли сильную связность?$\delta^+(G)+\delta^-(G) \geq n$

(Обратите внимание, что хотя граф, очевидно, должен быть сильно связан, чтобы он был гамильтоновым, я спрашиваю, подразумевается ли это условие условиями степени).

Вариант, который я предложил, был на самом деле немного другим вариантом теоремы Вудала . Возможно, я видел это в книге Bang-Jensen и Gutin . На момент написания комментария я не проверял правильность книги. Поэтому, чтобы быть уверенным, что я написал график, он должен быть тесно связан. Кстати, это утверждение верно, потому что может быть интерпретировано как частный случай теоремы Вудала. Кроме того, не нужно строго требование подключения.

Это теорема 6.4.6 из книги Банг-Йенсена и Гутина :

$D$$n\ge 2$$\delta^+(x)+\delta^-(y) \ge n$$x$$y$$x$$y$$D$

Это означает, что ответом на вторую часть вашего вопроса также является «Да».

$n$$n$$k<n$$a,b,c$$e,d$$k_2$$e$$d$$d$$b$$b$$e$$e$$c$$e,d$$d$$b$$2$$4=5-1 = n-1$$n$

P.S1: Конечно, вышеупомянутая теорема справедлива для простых орграфов. то есть орграфы без петель или параллельных ребер.

P.S2: У меня сейчас нет хорошего Tex-инструмента. Так что изображение не очень хорошее.

Ответ на ваш второй вопрос утвердительный:

$\delta^+(G)+\delta^-(G) \ge n$$G$

$G$$\delta^+(G)+\delta^-(G) < n$$G$$S$$S$$T$$T$$S$$S$$\delta^+(G) \le \delta^+(S) \le |S|-1$$\delta^-(G) \le |T|-1$

Это расширение ответа @Mobius, чтобы показать более сильное утверждение:

$\delta^+ + \delta^- \geq n-1$$\forall u,v\in V, d(u,v)\leq 2$

Доказательство:

$(u,v)\in E$

$A=\{x\in V: (u,x)\in E\}, B=\{y\in V: (y,v)\in E\}$

$(u,v)\not \in E$$A \cup B \subseteq V\setminus \{u,v\}$$|A\cup B|\leq n-2$

$|A\cap B| \geq 1$$\exists w\in V:(u,w),(w,v)\in E$$d(u,v)=2$

$\blacksquare$