キムラ　ケンジ   Kenji kimura   木村　健司    所属   石巻専修大学  理工学部    職種   准教授
言語種別	英語
発行・発表の年月	2014
形態種別	研究論文（学術雑誌）
標題	Defensive alliances with prescribed and proscribed vertices
執筆形態	共著
掲載誌名	University of Manitoba・CONGRESSUS NUMERANTIUM
巻・号・頁	220,pp.219-226
総ページ数	8
著者・共著者	川浦 貴博、仁木 直人
概要	Let $G = (V, E)$ be a graph with vertex set $V$ and edge set $E$. We denote by $N(v)$ the neighborhood of a vertex $v \in V$. A non-empty set of vertices $S \subset V$ is said to be an defensive alliance if for every vertex $v \in S$, $|N(v) \cap S| + 1 \ge |N(v) \cap (V - S)|$. Fricke et al. [A note on defensive alliances in graphs, \textit{Bulletin of the ICA}.\ \textbf{38} (2003) 37--41] have proved that every graph of order $n\ge 2$ has a defensive alliance of order at most $\lceil \frac{n}{2} \rceil$. Let $K \subset V$, $M\subset (V-K)$. Then, we consider a defensive alliance $S$ with $K \subset S \subset (V-M)$. In this talk, we show some upper bounds of order %results that of a defensive alliance for any pair of $(G, K, M)$.