مقدار ويژه 1- و گراف‌هاي فاقد مثلث

Eigenvalue −1 and triangle-free graphs

تعيين مرتبه ماكسيمم در بين گراف‌هايي كه ماتريس مجاورتشان داراي مقدار ويژه mu با چندگانگي ثابت k هستند، يكي از مسائلي است كه توسط محققين مختلفي مورد مطالعه قرار گرفته است. در اين ميان، شرايط اين مسأله براي مقدار ويژه‌هاي -1,0 با ساير مقادير ويژه متفاوت است. در اين مقاله اين مسأله را براي گراف‌هاي فاقد مثلث و براي مقدار ويژه mu=-1 مورد بررسي قرار مي‌دهيم. به‌عنوان نتيجه اصلي اين مقاله نشان مي‌دهيم مرتبه يك گراف همبند فاقد مثلث با درجه ماكسيمم d و مقدار ويژه -1 با چندگانگي k>1، حداكثر برابر k+d+1 است. به‌علاوه گراف‌هايي كه براي آن‌ها تساوي رخ مي‌دهد را رده‌بندي مي‌كنيم. اثبات اين نتيجه مبتني بر تكنيك مكمل ستاره‌اي است.

Determining the maximum order of graphs whose adjacency matrices have an eigenvalue μ with multiplicity k, is a problem which has been studied by several authors. The situation of the problem is quite different for the eigenvalues −1, 0. In this paper, we investigate this problem for triangle-free graphs and for the eigenvalue μ = −1. As the main result of the paper, we prove that the order of graphs with maximum degree d and the eigenvalue −1 with multiplicity k > 1 is at most k + d + 1. We also characterize the graphs attainting the lower bound.