Does

11

Denota por o grau mínimo de saída em e por o mínimo de grau. $\delta^+(G)$ $G$ $\delta^-(G)$

Em uma pergunta relacionada , mencionei a extensão Ghouila-Houri do teorema de Dirac nos ciclos hamiltonianos , o que sugere que se então G é hamiltoniano. $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$

Em seu comentário, Saeed comentou uma extensão diferente que parece mais forte, exceto que exige que o gráfico esteja fortemente conectado.

A forte conectividade foi comprovadamente redundante para o teorema de Ghouila-Houri cerca de 30 anos após sua primeira publicação, e eu queria saber se o mesmo vale para a extensão apresentada por Saeed.

Então a questão é:

Quem provou (alguém pode encontrar a referência) que implica que é hamiltoniano, dado que está fortemente conectado? $\delta^+(G)+\delta^-(G) \geq n$ $G$ $G$

A forte conectividade também é redundante aqui, ou seja, implica conectividade forte? $\delta^+(G)+\delta^-(G) \geq n$

(Observe que, embora o gráfico obviamente precise estar fortemente conectado para que seja hamiltoniano, estou perguntando se essa condição está implícita nas condições do grau).

reference-request graph-theory RB
fonte

8

A variação que sugeri foi na verdade uma variação ligeiramente diferente do teorema de Woodal . Talvez eu tenha visto no livro de Bang-Jensen e Gutin . No momento em que escrevi um comentário, não verifiquei o livro quanto à correção. Portanto, para ter certeza de que escrevi, o gráfico deve estar fortemente conectado. Aliás, essa afirmação vale porque pode ser interpretada como um caso especial do teorema de Woodal. Além disso, não é necessário um forte requisito de conectividade.

Este é o teorema 6.4.6 do livro de Bang-Jensen e Gutin :

Seja um dígrafo de ordem . Se para todos os pares de vértices e tal forma que não exista arco de a , então é hamiltoniano. $D$ $n\ge 2$ $\delta^+(x)+\delta^-(y) \ge n$ $x$ $y$ $x$ $y$ $D$

Isso significa que a resposta para a segunda parte da sua pergunta também é Sim.

$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$

insira a descrição da imagem aqui

P.S1: Certamente o teorema mencionado acima vale para dígrafos simples. ou seja, dígrafos sem arcos ou arestas paralelas.

P.S2: Eu não tenho uma boa ferramenta Tex no momento. Então, a imagem não é boa.

Saeed
fonte

3

Quando há apenas dois autores, é melhor consultá-los como "Primeiro e Segundo", em vez de "Primeiro et al.", Para que recebam o crédito que merecem. Et al. ("e outros") só deve ser usado quando a lista completa de autores for longa o suficiente para reproduzi-la.

David Richerby

7

A resposta para sua segunda pergunta é afirmativa:

$\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$

δ^{+} (G) + δ^{-} (G) \leq | S | + | T | - 2 \leq n - 2 .

$\delta^+(G)+\delta^-(G) \le |S|+|T|-2 \le n-2 \ .$

bolinho de massa mobius
fonte

11

\geq n - 1

$\ge n-1$

@GeoffreyIrving Sim, parece que sim.

mobius dumpling

Isso me faz pensar se n-1 é suficiente para Hamiltonicidade.

RB

@RB, Não, não é suficiente.

Saeed

11

δ^{-} + δ^{+} = n - 1

$\delta^-+\delta^+ = n-1$

4

Esta é uma extensão da resposta do @Mobius para mostrar uma afirmação mais forte:

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

Prova:

$(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$

n - 1 \leq δ^{+} + δ^{-} \leq | A | + | B | = | A \cup B | + | A \cap B | \leq n - 2 + | A \cap B |

$n-1 \leq \delta^+ + \delta^- \leq |A|+|B| = |A\cup B| + |A\cap B| \leq n-2 + |A\cap B|$

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

$\blacksquare$

RB
fonte

Does

Respostas: