عدد زیرتقسیم m - امن دایم در گرافها

Abstract

فرض کنید گرافی با مجموعه رئوس و مجموعه یالهای باشد. مجموعه را یک مجموعه احاطه گر در نامند هرگاه هر رأس از با حداقل یک رأس از مجاور باشد. مجموعه احاطه گر از گراف را یک مجموعه 1- امن دایم گویند هرگاه به ازای هر عدد صحیح مثبت و هر دنباله از رئوس، دنباله ای مانند با شرط موجود باشد که یا و یک مجموعه احاطه گر باشد. اگر روی هریک از رئوس یک مجموعه 1- امن دایم در یک محافظ قرار دهیم، آنگاه به ازای هر دنباله از حملات به رئوس، با حرکت یک محافظ در امتداد یکی از یالهای مجاور آن، مجموعه حاصل، باز هم امن باقی می ماند. اگر به ازای هر دنباله از حملات به رئوس ، تمام محافظان بتوانند در امتداد یکی از یالهای مجاور حرکت کنند و مجموعه حاصل باز هم امن بماند، آنگاه این مجموعه را یک مجموعه امن دایم نامند. کمترین تعداد اعضای یک مجموعه امن دایم را عدد امن دایم نامیده و با نشان می دهند. زیرتقسیم یال از عبارت است از حذف و افزودن رأس جدید و یالهای و . عدد زیرتقسیم امن دایم ، ، عبارت است از کمترین تعداد یالهایی از که با زیرتقسیم آنها عدد امن دایم گراف افزایش می یابد. در این مقاله نشان می دهیم که عدد زیرتقسیم امن دایم در[a1] هر گراف حداکثر 3 است.

[a1]