31551

پراكندگي مقادير ويژه ماتريس لاپلاسين وپارامتر‌هاي گراف

دكتري

رياضي

1399

10.07.1403

پروفسور مهدي علائيان

پروفسور سعيد اكبري

رياضي و علوم كامپيوتر

ماﺗﺮﯾﺲ ﻫﺎﯼ ﻣﺘﻔﺎﻭتي ﺑﻪ ﮔﺮﺍﻑ ﻧﺴﺒﺖ ﺩﺍﺩﻩ ميﺷﻮﺩ. ﺑﺮﺍﯼ ﺷﻨﺎﺳﺎﯾﯽ ﻭﯾﮋگيﻫﺎﯼ ﻭ ﺳﺎﺧﺘﺎﺭ ﮔﺮﺍﻑ ميﺗﻮﺍﻥ ﺍﺯ ﺍﯾﻦ ﻣﺎﺗﺮﯾﺲ ﻫﺎ ﺍﺳﺘﻔﺎﺩﻩ ﮐﺮﺩ. يكي ﺍﺯ ﺍﺑﺰﺍﺭﻫﺎﯼ ﻣﻄﺎﻟﻌﻪ ﮔﺮﺍﻑﻫﺎ ﺑﻪ كمك ﻣﺎﺗﺮﯾﺲﻫﺎﯼ ﺁﻧﻬﺎ، ﻣﻘﺎﺩﯾﺮ ﻭﯾﮋﻩ ﺍﯾﻦ ﻣﺎﺗﺮﯾﺲ ﻫﺎ ﺍﺳﺖ. ﺩﻭ ﻣﻮﺭﺩ اﺯ ﻣﻬﻤﺘﺮﯾﻦ ﺍﯾﻦ ﻣﺎﺗﺮﯾﺲﻫﺎ، ﻣﺎﺗﺮﯾﺲ ﻣﺠﺎﻭﺭﺕ ﻭ ﻣﺎﺗﺮﯾﺲ ﻻﭘﻼﺳﯿﻦ ﮔﺮﺍﻑ مي ﺑﺎﺷﺪ. ﺩﺭ ﺍﯾﻦ ﺭﺳﺎﻟﻪ ﭘﺮﺍﮐﻨﺪگي ﻣﻘﺎﺩﯾﺮ ﻭﯾﮋﻩ ﻻﭘﻼﺳﯿﻦ ﮔﺮﺍﻑ ﺭﺍ ﻣﻄﺎﻟﻌﻪ ميﮐﻨﯿﻢ. براي گرافG و بازهI تعداد مقادير ويژه ماتريس لاپلاسين G در بازه I را با نماد m_G I نشان مي‌دهيم. ابتدا در مورد رابطه بين مقادير ويژه لاپلاسين و عدد پوشش يالي يك گراف تحقيق مي‌كنيم. فرض كنيم βʹ(G) عدد پوشش يالي گرافG باشد، نشان مي‌دهيم m_G [1,n]≥βʹ(G) و به‌طور خاص نشان مي‌دهيم m_G [1,n]≥βʹ(G)+1. همچنين نشان مي‌دهيم m_G (n-1,n]≤(G)، كه در آن(G) عدد همبنديG است. در ادامه تمام درخت‌هايي را رده‌بندي مي‌كنيم كه در آن داشته باشيم=j m_T (n-i,n] براي1≤i,j≤2 . بعلاوه تعداد گراف‌هاي را رده‌بندي مي‌كنيم كه تعداد مشخصي مقدار ويژه لاپلاسين در زير بازه‌هاي[0,n] كه بر حسب دنباله درجات مشخص شده‌اند داشته باشند. نشان مي‌دهيم m_G [d_n,n]=2 اگر و تنها اگرG∈{P_3,P_4,C_3,C_5}. همچنين تمام گراف‌هايي را مشخص مي‌كنيم كه در آن‌ها داشته باشيم m_G [d_(n-1),n]=2 . بعلاوه، تمام گراف‌هايي را رده‌بندي مي‌كنيم كه در آن‌ها رابطه m_G [0,d_1]=2 برقرار باشد.

1403/08/29

Laplacian Eigenvalue Distribution and Graph Parameters

10/1/2025 12:00:00 AM

In this thesis, we study the Laplacian eigenvalues distribution of a graph. For a connected graph G of order n and an interval I, we denote by mGI the number of Laplacian eigenvalues of G in I. We present some bounds for mGI in terms of the structural parameter β′(G), the edge covering number of G. We prove a known result that mG [1, n] ≥ β′(G). We also show that all graphs G ̸= C3,C7 with minimum degree at least two, mG [1, n] ≥ β′(G)+1, where n is the number of vertices G. We present a short proof of the known result that mG (n − 1, n] ≤ κ(G), where κ(G) is the vertex connectivity of G. Additionally, we classify all trees T such that mT (n − i, n] = j, for 1 ≤ i, j ≤ 2. Finally, we present some bounds on the number of Laplacian eigenvalues contained in the various subintervals of [0, n] in terms of the degree sequence of G. Let d1 ≥ · · · ≥ dn be the degree sequence of a graph G. We show that mG[dn, n]=2 if and only if G ∈ {P3, P4,C3,C5}. We also characterize all graphs of order n for which mG[dn−1, n]=2. Moreover, we classify all graphs such that mG[0, d1] = 2.

ماتريس لاپلاسين، , مقادير ويژه لاپلاسين , پوشش يالي , عدد همبندي , عدد همبندي

Laplacian matrix , Laplacian eigenvalue , Edge covering number , Vertex connectivity , Degree sequence.

Ⅿostafa Ⅾarougheh

Prof. Mehdi Alaeiyan