On the efficiency index of a graph
Tóm tắt
A graph
$$G$$
has an efficient dominating set
$$D \subseteq V(G)$$
if
$$D$$
dominates every vertex exactly once. In this paper we introduce the study of the family
$${S_k}$$
of graphs for which every
$$G-S$$
is efficiently dominatable for
$$0 \le |S|\le k$$
. Assuming that
$$G$$
is efficiently dominatable, the efficiency index is the largest value k for which
$$G$$
is in
$$S_k$$
. A graph
$$G$$
will be called super-efficient if every induced subgraph is efficiently dominatable. We give some characterizations for trees, grids, cylinders and torii to be super-efficient.
Tài liệu tham khảo
Bange DW, Barkauskas AE, Slater PJ (1978) Disjoint dominating sets in trees. Sandia Laboratories Report SAND 78–1087J
Bange DW, Barkauskas AE, Slater PJ (1988) Efficient dominating sets in graphs. In: Ringeisen RD, Roberts FS (eds) Applications of discrete mathematics. SIAM, Philadelphia, pp 189–199
Bange DW, Barkauskas AE, Slater PJ (1986) Efficient near-domination of grid graphs. Congr Numer 58:83–92
Bange DW, Barkauskas AE, Host LH, Slater PJ (1996) Generalized domination and efficient domination in graphs. Discrete Math 159:1–11
Barbosa R, Slater PJ (2012) On efficient dominating sets in simplicial graphs. J Comb Math Comb Comput 81:129–134
Biggs N (1973) Perfect codes in graphs. J. Combin Theory Ser B 15:289–296
Tamizh Chelvam T, Mutharasu S (2011) Efficient domination in Cartesian products of cycles. J Adv Pure Math 3:42–49
Dejter IJ (2008) Perfect domination in regular grid graphs. Australas J Comb 42:99–114
Grinstead DL, Slater PJ (1990) Fractional domination and fractional packing in graphs. Congr Numer 71:153–172
Grinstead DL, Slater PJ (1994) A recurrence template for several parameters in series-parallel graphs. Discrete Appl Math 54:151–168