چند جمله‌ای مشخصه لاپلاسی ادغام دو گراف

Abstract

فرض کنید $G_1$ و $G_2$ گراف‌های ساده با مجموعه راس‌های $V_1$ و $V_2$ و مجموعه یال‌های $E_1$ و $E_2$ باشند. با شناسایی دو خوشه $C_1 \subseteq V_1$ و $C_2 \subseteq V_2$ با مرتبه یکسان $t$ و جایگزینی آنها با خوشه $C^*$ ادغام دو گراف حاصل می‌گردد، که با نماد $G_1\circ_t G_2$ نمایش داده می‌‌شود. درصورتی که $t$ برابر یک یا دو باشد، به ترتیب ادغام راسی و یالی گراف نامیده می‌شود. فرض کنید $A$ ماتریس مجاروت و $D$ ماتریس قطری درجات گراف باشند، در این صورت ماتریس لاپلاسی یک گراف به صورت $ L=D-A$ تعریف می‌‌‌شود. چند جملهای مشخصه لاپلاسی گراف به صورت $\varphi(G)=\det(\mu I-L)$ تعریف می‌گردد. دراین مقاله به بررسی چند جملهای مشخصه لاپلاسی ادغام راسی و یالی دو گراف می‌پردازیم.