21581

21581

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

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

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

1398

1398/8/27

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

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

رياضي

در اين پايان‌نامه به بررسي دومين كوچكترين مقدار‌ويژه ماتريس‌لاپلاسي گراف 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.

1398/10/24

Algebraic connectivity of graphs

11/18/2019 12:00:00 AM

This thesis is a survey of the second smallest eigenvalue of the Laplacian of a graph G, best-known as the algebraic connectivity of G, denoted a(G)=λ_2 (G). And on the Laplacian spread of a graph G with n vertices is defined to be L(G)=D(G)-A(G), where λ_n (G) and λ_2 (G) are the largest and the Second smallest laplacian eigenvalues of G , respectively. Let λ_2 (G) denote its second smallest laplacian eigenvalue, It was conjectured that{λ_2 (G)+λ_2 (G ̅ )}≥1, where G ̅ is the Complement of G . Finally, in this thesis we prove that max⁡{λ_2 (G),λ_2 (G ̅)≥2/5.