Apakah

11

Dilambangkan dengan tingkat keluar minimal dalam , dan oleh yang minimal dalam derajat. $\delta^+(G)$ $G$ $\delta^-(G)$

Dalam pertanyaan terkait , saya telah menyebutkan perluasan Ghouila-Houri dari teorema Dirac pada siklus Hamilton , yang menunjukkan bahwa jika maka G adalah Hamiltonian. $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$

Dalam komentarnya, Saeed mengomentari ekstensi berbeda yang tampaknya lebih kuat, kecuali itu membutuhkan grafik untuk terhubung dengan kuat.

Konektivitas yang kuat terbukti berlebihan untuk teorema Ghouila-Houri sekitar 30 tahun setelah pertama kali diterbitkan, dan saya bertanya-tanya apakah hal yang sama berlaku untuk ekstensi yang disajikan Saeed.

Jadi pertanyaannya adalah:

Siapa yang membuktikan (adakah yang dapat menemukan referensi) bahwa menyiratkan adalah Hamiltonian, mengingat bahwa sangat terhubung? $\delta^+(G)+\delta^-(G) \geq n$ $G$ $G$

Apakah konektivitas kuat juga ada di sini, yaitu Apakah menyiratkan konektivitas yang kuat? $\delta^+(G)+\delta^-(G) \geq n$

(Perhatikan bahwa sementara grafik jelas harus sangat terhubung agar menjadi Hamiltonian, saya bertanya apakah kondisi ini tersirat oleh kondisi derajat).

reference-request graph-theory BPR
sumber

8

Variasi yang saya sarankan sebenarnya variasi yang sedikit berbeda dari teorema Woodal . Mungkin saya melihatnya di buku Bang-Jensen dan Gutin . Pada saat saya menulis komentar, saya tidak memeriksa kebenarannya. Jadi untuk memastikan saya menulis grafik harus terhubung dengan kuat. BTW, pernyataan itu berlaku karena dapat diartikan sebagai kasus khusus teorema Woodal. Selain itu tidak perlu persyaratan konektivitas kuat.

Ini adalah teorema 6.4.6 dari buku Bang-Jensen dan Gutin :

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

Itu berarti jawaban untuk bagian kedua dari pertanyaan Anda juga Ya.

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

masukkan deskripsi gambar di sini

P.S1: Tentu saja teorema tersebut berlaku untuk digraf sederhana. yaitu digraf tanpa loop atau tepi paralel.

P. S2: Saya tidak memiliki alat Tex yang bagus saat ini. Jadi image tidak bagus.

Saeed
sumber

3

Ketika hanya ada dua penulis, lebih baik untuk merujuk mereka sebagai "Pertama dan Kedua", daripada "Pertama et al.", Sehingga mereka menerima kredit yang layak mereka dapatkan. Et al. ("dan lain-lain") hanya boleh digunakan ketika daftar penulis lengkap cukup panjang sehingga mereproduksinya akan menjadi canggung.

David Richerby

7

Jawaban untuk pertanyaan kedua Anda adalah afirmatif:

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

pangsit mobius
sumber

1

\geq n - 1

$\ge n-1$

@ GeoffreyIrving Ya, sepertinya begitu.

Mobius dumpling

Ini membuat saya bertanya-tanya apakah n-1 sudah cukup untuk Hamiltonicity.

RB

@RB, Tidak, itu tidak cukup.

Saeed

1

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

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

4

Ini adalah perpanjangan dari jawaban @Mobius untuk menunjukkan klaim yang lebih kuat:

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

Bukti:

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

BPR
sumber

Apakah

Jawaban: