مجله بین المللی ترکیبات
سال:1390 | دوره:1 | شماره:1 |تعداد مقالات:7

گرافهای یال فاصله- متعادل، گرافهایی هستند که درآنها برای هر یال e=uv تعداد یال های نزدیک تر به راس u تا به راس v، برابر با تعداد یال های نزدیکتر به v تا به u است. در این مقاله این خاصیت را تحت برخی اعمال گرافی مطالعه می کنیم.

فرض کنیم K یک عدد صحیح مثبت باشد. یک زیر مجموعه 𝑆 از V(G) دریک گراف G یک مجموعه احاطه گر کلی -K تائی از G نامیده می شود اگر هر راس از G حداقل K همسایه در S داشته باشد. عدد احاطه گر کلی –K تائی از تعداد عناصر مجموعه ای احاطه گر کلی -K تائی از G که دارای کمترین تعداد عضو بین چنین مجموعه هایی است. در این مقاله برای یک گراف داده شده G با حداقل درجه کمتر یا مساوی K، چندکران دقیق بالا و پایین برای عدد احاطه گر -K کلی تائی از گراف -m مایسیلکین mm(G)از G را برحسب K و gxk,t(G) بدست می آوریم. به ویژه کران های دقیق gxk,t(G)+1 و gxk,t(G)+k برای gxk,t(m1(G)) ارائه می کنیم، و گرافهایی با خاصیت gxk,t(m1(G))=gxk,t(G)+1 را مشخص می کنیم.

فرض کنید G=(v, E) یک گراف ساده همبند باشد. یک برچسب گذاری f:V®Z2 دو برچسب گذاری یالی f+, f*:E®Z2 تعریف شده به صورت f+(xy)=f(x) +f(y) و f*(xy)=f(x) f(y) برای هر xyÎE را القاء می کند. به ازای iÎZ2 فرض می کنیم ef*(i)=|(f*)-1(i)| و uf(i)=|f-1(i)|, ef+ (i)=|(f+)-1(i)|. یک برچسب گذاری 𝑓 دوستانه نامیده می شود اگر |uf (1)-uf (0)| £ 1 باشد. برای یک برچسب گذاری دوستانه 𝑓 از یک گراف G، شاخص دوستانه G تحت 𝑓 به صورت if+ (G)=ef+(1)-ef+(0) تعریف می شود. مجموعه {𝑓 یک برچسب گذاری دوستانه از G باشد if+(G)|} مجموعه کامل شاخص دوستانه از G تعریف می شود. هم چنین ضرب شاخص- صمیمی از G تحت 𝑓 به صورت if*(G)=ef*(1)-ef*(0) تعریف می شود. مجموعه {𝑓 یک نشان دوستانه از G است if*(G)|} مجموعه کامل شاخص های ضرب- صمیمی از G است. در این مقاله یک رابطه بین شاخص دوستانه و شاخص ضرب- صمیمی از یک گراف منظم را پیدا می کنیم. به عنوان کاربرد، مجموعه های کامل شاخص های ضرب-صمیمی گراف های چنبره ای که توسط کونگ، لی و ان جی در سال 2010 پرسیده شده است را تعیین می کنیم، و همچنین شاخص های مربوط به دور ها را نیز تعیین می کنیم.

گراف NC- احاطه گر مینیمال MCN (G)، گراف CN- احاطه گر مینیمال اشتراکی CMCN (G) و گراف –CN احاطه گر مینیمال راسی MvCN (G) را تعریف می کنیم و مشخص سازی هایی را برای اینکه این گراف های تعریف شده اخیر برای یک گراف داده شده G همبند باشند، ارایه می شود. چندین نتیجه جدید دیگر نیز در خصوص این گراف های جدید ارایه می شود.

در این مقاله، عدد رنگی ستاره ای گراف مرکزی از گراف دو بخشی کامل و گراف تاجی گراف کامل با مسیر و دور را به دست می آوریم.

کار قبلی خود در مورد شاخص های پیچدگی مساله فروشنده دوره گرد را با استفاده از تکنیکهای طیفی گراف از بازیابی اطلاعات گسترش می دهیم. یک شاخص پیچیدگی پایایی از یک نمونه I است که توسط آن می توانیم زمان اجرای یک الگوریتم دقیق برای TSP برای I را پیش بینی کنیم. مساله فروشنده دوره گرد متقارن با نمونه های I را در نظر می گیریم که توسط گراف های کامل وزن دار G نمایش داده شده اند. شهودا، سختی نمونه G به نحوه توزیع یال های کوتاه G مرتبط است. بنابراین تعدادی از زیرگراف های یالی کوتاه از G (درخت فراگیر مینیمال و چندین گراف دیگر) به عنوان گرا فهای غیر وزن دار و چندین مورد پایا از آنها را به عنوان شاخص های پیچیدگی بالقوه در نظر می گیریم. در اینجا پایاهای طیفی (مانند شعاع طیفی ماتریس مجاورت) نقش مهمی را بازی می کند. الگوریتم های خوشه بندی طیفی به همراه اطلاعات به دست آمده از شکاف طیفی در طیف لاپلاسی زیر گراف های یال کوتاه به کار برده شده است.

یک زیر مجموعه S از رئوس گراف G=(V, E) بدون راس تنها یک مجموعه غالب کلی نامیده می شود اگر هر راس از V (G) مجاور راسی در 𝑆 باشد. عدد غالبی کلی یک گراف G ماکسیمم تعداد مجموعه های غالب کلی است که می توان مجموعه رئوس G را به آنها افراز کرد. نشان می دهیم که عدد غالبی کلی یک گراف تصادفی -r منظم تقریبا به طور قطع حداکثر r-1 است، و برای گرافهای تصادفی -3 منظم، عدد غالبی کلی تقریبا به طور قطع برابر 2 است. همچنین یک کران پایین برای عدد غالبی کلی یک گراف بر حسب مرتبه، حداقل درجه و حداکثر درجه به دست می آوریم. به عنوان یک نتیجه فرعی، ثابت می کنیم که عدد غالبی کلی یک گراف -r منظم حداقل r/(3ln(r)) است.