On the efficiency index of a graph |
| |
Authors: | Rommel Barbosa Peter Slater |
| |
Institution: | 1.Instituto de Informatica,Universidade Federal de Goias,Goiania,Brazil;2.Department of Computer Science and Department of Mathematical Sciences,University of Alabama,Huntsville,USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|