بخشی از مقاله
چکیده
در این مقاله ابتدا به معرفی اجمالی چند جمله ای خوشه ای یک گراف می پردازیم. در ادامه نشان می دهیم که تمام ر یشه های چند جمله ای خوشه ای گرافهای وتری مسطح همبند خالی از ۴K حقیقی می باشند. به عنوان یک نتیجه ی بلافاصله، یک اثبات تابع مولدی برای قضیه ی توران در مورد گرافهای مسطح همبند خالی از ۴K ارائه می دهیم. در پایان نیز چندین پرسش و حدس باز در مورد ر یشه های حقیقی چند جمله ای خوشه ای مطرح می کنیم.
مقدمه
» چند جمله ای وابستگی « برای اولین بار توسط فیشر ]١[، زمانی که وی روی یک مساله ی » نظریه ی گروه ترکیبیاتی « که مربوط به شمارش رده ی خاصی از کلمات بود کار می کرد، معرفی گردید. مساله این است که یک الفبا که یک مجموعه ی متناهی شامل m حرف است داریم و بعضی از این حروف با یکدیگر » جابجا « می شوند. هدف در واقع شمارش تعداد کلمات - n حرفی بدست آمده از این الفبا می باشد.
برای مجموعه الفبای S، می توان یک گراف وابستگی GS به صورت زیر نسبت داد: راسهای این گراف را همان حروف S می گیریم و دو راس - حرف - به هم در این گراف متصلند هرگاه حروف متناظرشان با یکدیگر جابجا شوند. فیشر ]١[ نشان داد که » تابع مولد « مساله ی ترکیبیات شمارشی بالا در واقع برابر با می باشد. اگر ما تمام علامتهای منفی ضرایب چند جمله ای fG - x - را به مثبت تغییر دهیم، چند جمله ای به دست می آید که به » چند جمله ای خوشه ای « معروف است و آن را با نماد C - G; x - نمایش خواهیم داد.
حاجی ابوالحسن و مرحوم مهرآبادی ]٣[، نه تنها نشان دادند که چند جمله ای خوشه ای هر گراف ساده همواره یک ریشه حقیقی در بازه ی - ٠ ;١[ دارد بلکه ثابت کردند که » همگی « ریشه های چند جمله ای خوشه ای گرافهای خالی از ٣ - K خالی از مثلث - » حقیقی « می باشند. این نتیجه ی آخر، در واقع معادل با قضیه زیبای منتل ]۴[ است که در مورد بیشترین تعداد یالها در یک گراف خالی از مثلث می باشد.
اخیرا نویسنده ی این مقاله و بیات با معرفی چند جمله ای های خوشه ای تعمیم یافته ی مرتبه ی اول و دوم، یک اثبات جدید جبری برای قضیه توران ]۵[ که در مورد بیشترین تعداد یالها در گرافهای خالی از ١Kr+ است، ارائه داده اند. در این مقاله، ما همان مسیر تحقیقاتی را ادامه داده و قصد داریم تا چند جمله ای های خوشه ای یک زیر رده ی مهم از گرافهای تام، یعنی » گرافهای وتری « را مورد بررسی قرار دهیم. هدف نهایی پژوهشی که این مقاله سرآغاز آن است، » رده بندی « تمام گرافهایی است که » همگی « ر یشه های چند جمله ای خوشه ای آنها » حقیقی « می باشند.
