همبندي‌جبري گراف‌ها

كارشناسي ارشد

در اين پايان‌نامه به بررسي دومين كوچكترين مقدار‌ويژه ماتريس‌لاپلاسي گراف G مي‌پردازيم كه به عنوان همبندي‌جبري گراف G شناخته شده است و آن‌را به a(G)=λ_2 (G) نشان مي‌دهيم. اگر ماتريس مجاورت گراف G را به A(G) و ماتريس قطري از درجه هاي رئوس را با D(G) نشان دهيم، آن‌گاه ماتريس‌لاپلاسي G را به صورت L(G)=D(G)-A(G) ، و مقادير ويژه لاپلاسي G را به صورت 0=λ_1 (G)≤λ_2 (G)≤⋯λ_n (G) نشان مي‌دهيم، هم‌چنين گسترش‌لاپلاسي گراف G با n رأس به صورت Ls(G)=λ_n (G)-λ_2 (G) تعريف مي‌شود كه در آن λ_n (G) و λ_2 (G) به ترتيب، بزرگترين و دومين كوچكترين مقدار ويژه لاپلاسي‌ گراف G مي باشد. اگرλ_2 (G) ، دومين مقدار ويژه لاپلاسي باشد، آن‌گاه حدس زده شده كه {λ_2 (G)+λ_2 (G ̅ )}≥1. در اين پايان نامه، ثابت مي‌كنيم كه max⁡{λ_2 (G),λ_2 (G ̅)≥2/5.

193941

دانشگاه علم و صنعت ايران

دكتر زهره مستقيم

رياضي محض - جبر

دكتر مهدي علاييان