|
Abstract
|
یک تابع [1,2]-احاطه گر، تابعی است مانند $f:V(G)\longrightarrow\{ 0, 1\}$، به طوری که هر رأس $u$ با وزن صفر $(f(u)=0)$، حداقل با یک و حداکثر با دو رأس از $V(G)$با وزن 1
$(f(v)=1)$
مجاور باشد. وزن تابع
$f$
را نیز به صورت
$\sum_{v\in V(G)} f(v)$
تعریف کرده و با نماد $w(f)$
نشان می دهیم. عدد $[1,2]$-احاطه ای\ $\gamma_{[1,2]}(G)$، همان مینیمم وزن تابع $[1,2]$-احاطه گر در $G$ است.
تابع $[1,2]$-احاطه گر $f=(V_0, V_1)$
را یک تابع $[1,2]$-احاطه گر تام گوییم هرگاه به ازای هر
$ v\in V(G)$
،
$1\leq\sum_{u\in N(v) }f(u)\leq 2$. ما ضمن معرفی عدد احاطه ای $\gamma_{[1,2]}(G)$، روابط موجود بین این پارامتر و پارامتر های تعریف شده ی بالا را بررسی خواهیم کرد و همچنین کران هایی برای عدد $[1,2]$-احاطه ای ارائه داده و ثابت می کنیم که \[ \gamma(G)\leq \gamma_{[1,2]}(G)\leq n. \]
در ادامه گراف هایی را معرفی خواهیم کرد که در آن گراف ها، عدد $[1, 2]$-
احاطه ای با عدد احاطه ای و یا مرتبۀ گراف برابر می باشد.
همچنین نشان می دهیم که به ازای هر گراف $G$ از مرتبه $n$، داریم: $\gamma_{t[1,2]}(G) \leq \frac{4n}{5}$.
سپس گراف هایی را که در آنها تساوی برقرار است، دسته بندی کرده و گراف هایی را بررسی می کنیم که فاقد مجموعه های $[1, 2]$
تام هستند. همچنین گراف هایی را بررسی خواهیم کرد که در آنها دو عدد $[1, 2]$-
احاطه ای و عدد $[1, 2]$-
احاطه ای تام با هم برابرند.
|