مشخصه‌یابی طیفی هسته‌های گراف در گراف‌های منظم از نظر فاصله از طریق ماتریس‌های هم‌ریختی

مشخصه‌یابی طیفی هسته‌های گراف در گراف‌های منظم از نظر فاصله از طریق ماتریس‌های هم‌ریختی

محمداسماعیل نیکفر1

1) دانش آموخته دکتری ریاضیات، دکترای تخصصی ریاضی محض، دبیر ریاضی، آموزش و پرورش منطقه ۴، تهران، ایران

کد IOI مقاله : ABKH-ACACGF
محل انتشار : چهارمین کنفرانس بین المللی پژوهش های کاربردی در علوم انسانی، اقتصاد، مدیریت و حسابداری(icrhema.com)
چکیده :
    این مطالعه یک چارچوب طیفی و ترکیبی برای توصیف کامل بودن هسته در گراف‌های منظم-فاصله‌ای توسعه می‌دهد، ویژگی‌ای که در آن یک گراف یا خود یک هسته است یا یک گراف کامل را به عنوان هسته خود می‌پذیرد. با تکیه بر روش ماتریس همریختی که توسط رابرسون در زمینه حدس کامرون-کازانیدیس برای گراف‌های منظم-فاصله‌ای قوی معرفی شد، ما بررسی می‌کنیم که تا چه حد می‌توان این رویکرد را به گراف‌های منظم-فاصله‌ای با قطر دلخواه (d) تعمیم داد. چارچوب پیشنهادی، ساختار تقاطع، توزیع مقدار ویژه و دنباله‌های کسینوسی مرتبط با گراف‌های منظم-فاصله‌ای را برای استخراج محدودیت‌هایی بر اندومورفیسم‌ها و پس‌رفت‌های آنها در نظر می‌گیرد. به طور خاص، ما شرایط طیفی لازم را که بر وجود اندومورفیسم‌های گراف حاکم است و تصاویر آنها قطری اکیداً کمتر از (d) دارند، به دست می‌آوریم. این شرایط منجر به نتیجه سفتی برای گراف‌های منظم-فاصله‌ای اولیه می‌شود: هر زمان که زیرگراف القا شده توسط رئوس در حداکثر فاصله از یک راس مشخص متصل شود، هر پس‌رفت به زیرگرافی با قطر (d) لزوماً یک خودریختی است. این قضیه، پدیده‌ی صلبیت مربوطه را برای گراف‌های قویاً منظم، که به عنوان حالت قطر-دو مطرح می‌شود، تعمیم می‌دهد. نتایج نظری با بررسی‌های محاسباتی گراف‌های فاصله-منظم با قطر سه تکمیل می‌شوند. در دسته‌ی مورد بررسی، هیچ گراف فاصله-منظم غیر دوبخشی و متضاد با ظرفیت حداکثر (50) یک اندومورفیسم را روی زیرگرافی با قطر دو نمی‌پذیرد. علاوه بر این، ما آرایه‌های تقاطع متعددی مربوط به گراف‌های فاصله-منظم اولیه با قطر سه را شناسایی می‌کنیم که معیار کامل بودن هسته را برآورده می‌کنند. با ادغام شواهد محاسباتی با تکنیک‌های تثبیت‌شده از نظریه‌ی جبری گراف، از جمله طرح‌های انجمنی، خودتوان‌های طیفی و تحلیل آرایه‌ی تقاطع، این تحقیق یک رویکرد سیستماتیک برای درک تعامل بین محدودیت‌های طیفی، همریختی‌های گراف و ساختار هسته در گراف‌های فاصله-منظم ایجاد می‌کند.

کلمات کلیدی : نظریه گراف‌های منظم از نظر فاصله ساختار هسته گراف ناورداهای طیفی گراف ماتریس‌های هم‌ریختی گراف صلبیت درون‌ریختی محدودیت‌های دنباله کسینوسی طرح‌های انجمنی عملگرهای تصویر طیفی تحلیل آرایه اشتراک بازگشت‌های گراف ترکیبیات جبری