به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
ارسال شده آبان ۲۲, ۱۴۰۲ در مطالب ریاضی توسط Dana_Sotoudeh (2,124 امتیاز)
برچسب گذاری دوباره آبان ۲۳, ۱۴۰۲ توسط Dana_Sotoudeh
456 بازدید

قضیه مورد نظر بدین صورت است: اگر $G$ یک گراف $n$ راسی باشد بطوری که $n \geq 2 $ باشد، آنگاه:

$$ \lceil { \frac{n}{1+ \bigtriangleup (G) }}\rceil \leq \gamma (G) $$

برهان

فرض کنیم $\gamma (G)=k$، یعنی $ S= {v_1,v_2,v_3,...,v_k} $ مجموعه احاطه گر مینیمم $G$ باشد چون هر راس $v_i$ به تعداد $ 1+deg(v_i) $ راس را احاطه می کند به طوری که $1 \leq i \leq k$ و رئوس $S$ گراف $G$ را احاطه می کند، پس: $$ \sum_{i=1}^{k}(1+deg(v_i)) \geq n $$ همچنین به ازای هر $i$ که $1 \leq i \leq k$ داریم: $ 1+deg(v_i) \leq1+ \bigtriangleup (G) $ پس:

$$ n \leq \sum_{i=1}^{k}(1+deg(v_i)) \leq k(1+ \bigtriangleup (G)) $$

پس

$$n \leq k(1+ \bigtriangleup (G)) \Longrightarrow \frac{n}{1+ \bigtriangleup (G) } \leq k=\gamma (G) $$

در نتیجه:

$$ \lceil { \frac{n}{1+ \bigtriangleup (G) }}\rceil \leq \gamma (G) $$


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...