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

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

کلیدواژه ها:

گراف فاقد مثلث ، مقدار ویژه ، تکنیک مکمل ستاره ای