Hypo-efficient domination and hypo-unique domination

Authors

Abstract: For a graph

G

let

g a m m a (G)

be its domination number. We define a graph G to be (i) a hypo-efficient domination graph (or a hypo-

m a t h c a l E D

graph) if

G

has no efficient dominating set (EDS) but every graph formed by removing a single vertex from

G

has at least one EDS, and (ii) a hypo-unique domination graph (a hypo-

m a t h c a l U D

graph) if

G

has at least two minimum dominating sets,but

G - v

has a unique minimum dominating set for each

v i n V (G)

. We show that each hypo-

m a t h c a l U D

graph

G

of order at least

3

is connected and

g a m m a (G - v) < g a m m a (G)

for all

v i n V (G)

. We obtain a tight upper bound on the order of a hypo-

m a t h c a l P

graph in terms of the domination number and maximum degree of the graph, where

m a t h c a l P i n m a t h c a l U D, m a t h c a l E D

. Families of circulant graphs which achieve these bounds are presented. We also prove that the bondage number of any hypo-

m a t h c a l U D

graph is not more than the minimum degree plus one.

Recommendations

This page was built for publication: Hypo-efficient domination and hypo-unique domination