外平面グラフに対するsecurity number

スポンサーリンク

概要

論文の詳細を見る
G=(V,E)をグラフとし,S={s_1,s_2,...,s_k}をVの部分集合とする.S上の攻撃とは,1≦i≦kに対してA_i⫅N[s_i]-Sであるような,互いに素なk個の集合A={A_1,A_2,...,A_k}であり,S上の防御とは,1≦i≦kに対してD_i⫅N[s_i]∩Sであるような,互いに素なk個の集合D={D_1,D_2,...,D_k}である.ここで,vの閉近傍をN[v]とかく.このとき,攻撃Aが防御可能とは,ある防御Dが存在し,1≦i≦kに対して,|D_i|≧|A_i|を満たすことをいう.そして,Sがセキュアとは,S上の全ての攻撃が防御可能であることをいう.Gのセキュリティ数とは,Gの最小なセキュア集合の大きさである.本論文では,任意の外平面グラフに対して,そのセキュリティ数が高々3であることを示す.
社団法人電子情報通信学会の論文
2008-03-03

著者

関連論文

もっと見る

スポンサーリンク