標題: Mutual transferability for (F, B, R)-domination on strongly chordal graphs and cactus graphs
作者: Chu, Kuan-Ting
Lin, Wu-Hsiung
Chen, Chiuyuan
應用數學系
Department of Applied Mathematics
關鍵字: Domination;Stability;Transferability;Strongly chordal graphs;Cactus graphs
公開日期: 30-Apr-2019
摘要: This paper studies a variation of domination in graphs called (F, B, R)-domination. Let G = (V, E) be a graph and V be the disjoint union of F, B, and R, where F consists of free vertices, B consists of bound vertices, and R consists of required vertices. An (F, B, R)-dominating set of G is a subset D subset of V such that R subset of D and each vertex in B - D is adjacent to some vertex in D. An (F, B, R)-2-stable set of G is a subset S subset of B such that S boolean AND N(R) = empty set and every two distinct vertices x and y in S have distance d(x, y) > 2. We prove that if G is strongly chordal, then alpha(F,B,R,2) (G) = gamma(F,B,R)(G)-vertical bar R vertical bar, where gamma(F,B,R)(G) is the minimum cardinality of an (F, B, R)-dominating set of G and alpha(F,B,R,2) (G) is the maximum cardinality of an (F, B, R)-2-stable set of G. Let D-1 ->* D-2 denote D1 being transferable to D-2. We prove that if G is a connected strongly chordal graph in which D-1 and D-2 are two (F, B, R)-dominating sets with vertical bar D-1 vertical bar = vertical bar D-2 vertical bar, then D-1 ->* D-2. We also prove that if G is a cactus graph in which D-1 and D-2 are two (F, B, R) -dominating sets with vertical bar D-1 vertical bar = vertical bar D-2 vertical bar, then D-1 boolean OR {1.extra} ->* D-2 boolean OR{1.extra}, where boolean OR{1.extra} means adding one extra element. (C) 2019 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.dam.2018.12,034
http://hdl.handle.net/11536/151927
ISSN: 0166-218X
DOI: 10.1016/j.dam.2018.12,034
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 259
起始頁: 41
結束頁: 52
Appears in Collections:Articles