· 2012· Ön baskı
Bir düzenli grafın bağımsız kümelerinin sayısı
The number of independent sets in a regular graph
- 104atıf
- 2012yıl
Kısa özet
N-köşeli, d-düzenli bir grafın bağımsız kümelerinin sayısı en fazla (2^(d+1)-1)^(N/2d)'dir; bu sınır, tam d-düzenli çiftli grafların ayrık birleşimleri için keskindir. Bu, Alon'un 1991 ve Kahn'ın 2001'deki tahminlerini kesin olarak çözer.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Ana noktalar
- N-köşeli, d-düzenli bir grafın bağımsız kümeleri için (2^(d+1)-1)^(N/2d) üst sınırı belirlenmiştir.
- Bu sınır keskindir ve tam d-düzenli çiftli grafların ayrık birleşimleri ile elde edilir.
- Sonuç, Alon (1991) ve Kahn (2001) tarafından ortaya atılan tahminleri kesin olarak çözmektedir.
- İspat, genel durumu çiftli duruma indirgeyen kısa bir yöntem sunmaktadır.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Özet (abstract)
Abstract. We show that the number of independent sets in an N-vertex, d-regular graph is at most (2 d+1 −1) N/2d, where the bound is sharp for a disjoint union of complete d-regular bipartite graphs. This settles a conjecture of Alon in 1991 and Kahn in 2001. Kahn proved the bound when the graph is assumed to be bipartite. We give a short proof that reduces the general case to the bipartite case. Our method also works for a weighted generalization, i.e., an upper bound for the independence polynomial of a regular graph. 1.
Yazarların özeti; kaynağından alınmıştır., 2012 · 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: Ayrık Matematik ve Kombinatorik
Discrete Mathematics and CombinatoricsMathematics