احاطه گر kمجاورت در گراف‌ها

فرض کنید g یک گراف ساده و بدون دور با مجموعه رئوس v باشد. یک مجموعه s که زیرمجموعه v است را احاطه‌گر گویند هرگاه هر راسی که خارج از s است با حداقل یک راس در s همجوار باشد. فرض کنید k≥1 عددی صحیح باشد. مجموعه احاطه‌گر s را یک مجموعه احاطه‌گر kمجاورت می‌نامیم هرگاه زیرگراف القائی g[s] شامل راسی از درجه حداکثر k1 باشد. کمترین تعداد عناصر یک مجموعه احاطه‌گر kمجاورت برای گراف g عدد احاطه kمجاورت آن گراف نامیده می‌شود و با نماد γ_k^a (g) نمایش داده می‌شود. در این مقاله، مطالعه احاطه‌گر kمجاورت آغاز می‌شود. سپس مقادیر دقیق و کران‌هایی برای عدد احاطه kمجاورت یک گراف داده شده ارائه می‌شود. همچنین، نشان داده می‌شود که یک الگوریتم با زمان چندجمله‌ای برای محاسبه عدد احاطه kمجاورت یک درخت داده شده وجود دارد. علاوه بر این، ثابت می‌شود که مسئله تصمیم‌گیری مرتبط با احاطه‌گر kمجاورت برای گراف‌های دوبخشی npکامل است.

kAdjacency Domination in Graphs

Let be a simple and undirected graph with vertex set . A set is called a dominating set of if every vertexoutside is adjacent to at least one vertex of . For any integer , a dominating set is called a adjacencydominating set of if the induced subgraph contains at least one vertex of degree at most . The minimumcardinality of a adjacency dominating set of is called the adjacency domination number of that isdenoted by . In this paper, the study of adjacency domination in graphs is initiated, and exact values andsome bounds on the adjacency domination number of a given graph are presented. Furthermore, it isshown that there is a polynomialtime algorithm that computes the adjacency domination number of agiven tree. Moreover, it is proven that the decision problem associated to the adjacency domination isNPcomplete for bipartite graphs.