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

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

Eigenvalue -1 and triangle-free graphs

Determining the maximum order of graphs whose adjacency matrices have an eigenvalue $mu$ 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 trianglefree graphs and for the eigenvalue $mu=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.