Some results on characterizing the edges of connected graphs with a given domination number |
| |
Authors: | Laura A Sanchis |
| |
Institution: | Department of Computer Science, Colgate University, Hamilton, NY 13346, USA |
| |
Abstract: | A dominating set for a graph G = (V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which {v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m1 (G, D) denote the number of edges that have neither endpoint in D, and let m2 (G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (m1 (G, D), m2 (G, D)) can attain for connected graphs having a given domination number. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|