Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949917 | Discrete Applied Mathematics | 2016 | 6 Pages |
Abstract
A non-empty subset S of the vertices of a connected graph G=(V(G),E(G)) is a safe set if, for every connected component C of G[S] and every connected component D of GâS, we have |C|â¥|D| whenever there exists an edge of G between C and D. If G[S] is connected, then S is called a connected safe set. We discuss the minimum sizes of safe sets and connected safe sets in connected graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shinya Fujita, Gary MacGillivray, Tadashi Sakuma,