圖形上的完全K-控制問題

Abstract

圖形Ｇ＝（Ｖ，Ｅ）的Ｋ控制集合是一滿足下列條件的點集合Ｄ：Ｖ中的每一點距離 Ｄ中的某一點在距離Ｋ以內，Ｇ的完全Ｋ控制集合是滿足下列條件的點集合Ｄ：Ｖ中 的每一點Ｖ距離Ｄ－｛ｖ｝中的某一點u 在距離Ｋ以內。一個圖形Ｇ的Ｋ控制數就是 在Ｇ中Ｋ控制集合元素最少的個數。Ｇ的完全Ｋ控制數就是在Ｇ中完全Ｋ控制集合元 素最少的個數。 Cockayne,Dawes和Hedetniemi提出完全控制的觀念，一個完全控制集合Ｄ是Ｖ中的每 一點都與Ｄ中的某些點相鄰接。因此我們提出完全Ｋ控制問題。 本論文中我們將證明，假如Ｇ是一個具有n≧ｋ+1 個點的連通圖，則它的Ｋ控制數小 於或等於ｎ╱（ｋ＋１）。假如Ｇ是一個具有n≧2ｋ＋１個點的連通圖，則它的完全 ｋ控制數小於或等於２ｎ╱（２ｋ＋１）。我們也提出一個演算法去找樹圖的最小完 全２控制集合。