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

فرض کنید G=(V,E) یک گراف ساده با n راس و m یال باشد. یک -r تطابق از G یک مجموعه از r یال است که هیچ دو تا از آنها راس مشترکی ندارند. اندیس هوسویا Z(G) از یک گراف G مجموع تعداد کل تطابق های آن است. یک مجموعه مستقل از G یک مجموعه از رئوس است که هیچ دوتای آنها با هم مجاور نیستند. اندیس مریفیلد-سیمونز G مجموع تعداد کل مجموعه های مستقل آن است. در این مقاله اندیس هوسویا و مریفیلد-سیمونز حاصلضرب تاجی دو گراف بدست آوره می شود.

در این مقاله دترمینان ماتریس های مجاورت گراف های با یک تعداد راس مشخص مورد مطالعه قرار می گیرند. با استفاده از اطلاعات گراف های با مرتبه کوچک تولید شده برندن مک کی، دترمینان گراف های با حداقل 9 راس محاسبه شده اند و تعداد گراف های غیر یکریخت با تعداد رئوس مشخص که دترمینان آنها با یک عدد برابر است در جدولی نمایش داده شده اند. با استفاده از ایده ای از ام. نیومن، ثابت شده است اگر G گرافی n راسی و m یالی باشد و {d1,…, dn} مجموعه درجات رئوس گراف G باشد، آنگاه gcd (2m, d2) d دترمینان ماتریس مجاورت G را می شمارد، جاییکه .d=gcd (d1,…, dn) دترمینان های ممکن ماتریس های مجاورت با دقیقا دو دور بدست آمده اند.

اولین (P1) و دومین (P2) اندیس های زاگرب ضربی یک گراف همبند G با مجموعه رئوس V(G) و مجموعه یال های E(G) به صورت P1 (G)=PuÎV(G) du2 وP2 (G)=PuvÎE(G) du dv ، به ترتیب تعریف می شوند، جاییکه du درجه راس u را نمایش می دهد. در این مقاله رویکردی ساده را برای مرتب کردن این اندیس ها برای گراف های همبند از مرتبه ای مشخص را ارایه می کنیم. علاوه بر این به عنوان کاربردی از این رویکرد ساده، مرتب سازی های شناخته شده اولین و دومین اندیس زاگرب ضربی برای برخی رده های گراف های همبند توسیع داده شده است.

فرض کنید G=(V,E) گرافی باp  راس و q یال باشد. یک پوشش گراف نمای غیر دوری از G یک گردایه Y از مسیرها در G است که به طور داخلی با هم مجزا هستند و هر یال گراف را دقیقا یک بار می پوشانند. فرض کنیدf:V ® {1,2,…,p}  یک برچسب گذاری دوسویی از رئوس گراف G باشد. فرض کنید Gf گراف جهتداری باشد که با جهتدهی به یال های uv از G از u به v به شرط اینکه f(u)<f(v) باشد، بدست آید. اگر مجموعه Yf از تمام مسیرهای جهتدار بیشین در ­Gf با نادیده گرفتن جهت ها یک پوشش گراف نمای غیردوری برای G باشد، در اینصورت f را یک برچسب گذاری گراف نمای G نامیده و G را یک گراف گراف نمای برچسبی می نامیم.و f} یک برچسب گذاری گراف نمای G استhl=min {|Yf |:  عدد پوششی گراف نمای برچسبی G نامیده می شود. در این مقاله گراف هایی که برای آنها (الف) hl=q-m، جاییکه m تعداد رئوس درجه 2 است و (ب) hl=q را مشخص می کنیم. عدد پوششی گراف نمای برچسبی را برای گراف های تک دوری تعیین می کنیم.

فرض کنید n، t1، …،tk  اعداد صحیح مثبت باشند. یک گراف تواپلیتز، گرافی چون G=(V,E) است با V={1,…,n} و .E= {(i, j) | |i-j| Î {t1,…,tk}} در این مقاله نتایجی راجع به تجزیه گراف های تواپلیتز بدست می آوریم.

هانسن و دیگران با استفاده از بسته نرم افزاری AutoGraphiX حدس زدند که اندیس سگد Sz(G) و اندیس وینر W(G) یک گراف دو بخشی همبند G با4£n  راس و n£m یال، از رابطه Sz(G)-W(G)³4n-8 پیروی می کند. علاوه بر این کران می تواند بهترین حالت ممکن باشد. در این مقاله یک اثبات برای این حدس ارایه می کنیم.

اندیس هوسویا و اندیس مریفیلد-سیمونز دو نوع پایای گرافی هستند که در شیمی ریاضی بکار برده می شوند. در این مقاله، فرمول هایی را برای محاسبه این اندیس ها برای حاصلضرب تاجی و اتصال دو گراف ارایه می کنیم. علاوه بر این، فرمول هایی دقیق برای اندیس های هوسویا و مریفیلد-سیمونز برای گراف های دو دوری، گراف های کرم صد پایی و دوگان ستاره بدست می آوریم.