عدد احاطه‌گری

عدد احاطه‌گری

تعریف

به تعداد رئوس مجموعه احاطه‌گر مینیمم یک گراف عدد احاطه‌گری آن گراف می‌گوییم.

سقف یک عدد

تعریف 

در صورتی که \(x\) عددی غیر صحیح باشد برای نمایش عدد صحیح بعد از \(x\) از \(\left\lceil x\right\rceil\)  استفاده می‌کنیم و آن را سقف \(x\) می‌خوانیم.

مثال

\(\left\lceil3.5\right\rceil\ =4\)           \(\left\lceil3\right\rceil\ =3\)           \(\left\lceil-1.5\right\rceil\ =-1\)

نکته

برای مجموعه اعداد \(\mathbb{Z}\) سقف و کف برابر است.

اگر \(G\) یک گراف \(n\) رأسی با ماکزیمم درجۀ \(\Delta\) باشد و \(D\) یک مجموعۀ احاطه‌گر در آن باشد، آنگاه \(\left\lceil \frac{n}{∆+1} \right\rceil\le \left| D \right|\) و از آنجا که \(\gamma(G)\) نیز اندازه یک مجموعۀ احاطه‌گر است همواره داریم \(\left\lceil \frac{n}{∆+1} \right\rceil\le\gamma(G)\)
بنابر این در گراف \(G\) عدد \(\left\lceil \frac{n}{∆+1} \right\rceil\) یک کران پایین برای \(\gamma(G)\) است و \(\gamma(G)\) نمی‌تواند از آن کمتر باشد.