|
|
|
|
maximal outerplanar graphs with semipaired domination number double the domination number
|
|
|
|
|
|
|
|
نویسنده
|
henning michael a. ,kaemawichanurat pawaton
|
|
منبع
|
communications in combinatorics and optimization - 2026 - دوره : 11 - شماره : 1 - صفحه:1 -20
|
|
چکیده
|
A subset $s$ of vertices in a graph $g$ is a dominating set if every vertex in $v(g) setminus s$ is adjacent to a vertex in $s$. if the graph $g$ has no isolated vertex, then a pair dominating set $s$ of $g$ is a dominating set of $g$ such that $g[s]$ has a perfect matching. further, a semipaired dominating set of $g$ is a dominating set of $g$ with the additional property that the set $s$ can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. the domination number $gamma(g)$ is the minimum cardinality of a dominating set of $g$. similarly, the paired (semipaired) domination number $gamma_{pr}(g)$ $(gamma_{pr2}(g))$ is the minimum cardinality of a paired (semipaired) dominating set of $g$. it is known that for a graph $g$, $gamma(g) le gamma_{pr2}(g) le gamma_{pr}(g) le 2gamma(g)$. in this paper, we characterize maximal outerplanar graphs $g$ satisfying $gamma_{pr2}(g) = 2gamma(g)$. hence, our result yields the characterization of maximal outerplanar graphs $g$ satisfying $gamma_{pr}(g) = 2gamma(g)$.
|
|
کلیدواژه
|
paired-domination ,semipaired domination number ,maximal outerplanar graphs
|
|
آدرس
|
university of johannesburg, department of mathematics and applied mathematics, south africa, king mongkut’s university of technology thonburi, department of mathematics, thailand
|
|
پست الکترونیکی
|
pawaton.kae@kmutt.ac.th
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|