Journal of Graph Theory· 2026Q1
Kübik Graflarda Dominasyon İçin 13-Kestirimler
The 13‐Conjectures for Domination in Cubic Graphs
- 1atıf
- Q1SCImago
- 2026yıl
Kısa özet
Bu çalışma, 7 veya 8 döngüsü olmayan kübik graflar için Verstraete kestirimini (girth >= 6 olan kübik bir grafın dominasyon sayısı en fazla n/3'tür) ve 4 veya 8 döngüsü olmayan iki parçalı graflar için Kostochka kestirimini (sırası n olan iki parçalı kübik bir grafın dominasyon sayısı en fazla n/3'tür) kanıtlamaktadır.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Ana noktalar
- 7 veya 8 döngüsü olmayan kübik graflar için Verstraete kestirimini kanıtlar.
- 4 veya 8 döngüsü olmayan kübik iki parçalı graflar için Kostochka kestirimini kanıtlar.
- Her iki kestirim de kübik grafların dominasyon sayısını, köşe sayısı n olmak üzere n/3 ile ilişkilendirir.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Özet (abstract)
ABSTRACT A set of vertices in a graph is a dominating set of if every vertex not in is adjacent to a vertex in . The domination number of , denoted by , is the minimum cardinality among all dominating sets in . In a breakthrough paper in 2008, Löwenstein and Rautenbach proved that if is a cubic graph of order and girth at least 83, then . A natural question is if this girth condition can be lowered. The question gave birth to two ‐conjectures for domination in cubic graphs. The first conjecture, posed by Verstraete in 2010, states that if is a cubic graph on vertices with girth at least 6, then . The second conjecture, first posed as a question by Kostochka in 2009, states that if is a cubic, bipartite graph of order , then . In this article, we prove Verstraete's conjecture when there is no 7‐cycle and no 8‐cycle, and we prove the Kostochka's related conjecture for bipartite graphs when there is no 4‐cycle and no 8‐cycle.
Yazarların özeti; kaynağından alınmıştır. Journal of Graph Theory, 2026 · DOI ↗
Ücretsiz hesapla devam et
Makaleye Sor ile bu makaleye günde 3 soru ücretsiz; makaleyi kaydet, kaynakçasını al, ilgi alanına göre her gün yeni özetler. Çıkarımlar Premium.
Web'de ücretsiz devam etGoogle ya da Apple hesabınla giriş; kart istemez. Bu makaleye geri dönersin.
Telefonda:
Alan: Hesaplamalı Kuram ve Matematik
Computational Theory and MathematicsComputer Science