Contributions to the theory of domination,independence and irredundance in graphs |
| |
Authors: | EJ Cockayne O Favaron C Payan AG Thomason |
| |
Institution: | University of Victoria, Victoria, B.C., Canada V8W2Y2;L.R.I., E.R.A. 452, Bât. 425, Université de Paris-Sud, 91405 Orsay,France;I.R.M.A. BP53X, 38041 Grenoble Cedex, France;D.P.M.M.S., 76 Mill Lane, Cambridge CB2 1SB, England |
| |
Abstract: | A vertex x in a subset X of vertices of an undirected graph is redundant if its closed neighbourhood is contained in the union of closed neighbourhoods of vertices of X?{x}. In the context of a communications network, this means that any vertex which may receive communications from X may also be informed from X?{x}. The lower and upper irredundance numbers ir(G) and IR(G) are respectively the minimum and maximum cardinalities taken over all maximal sets of vertices having no redundancies. The domination number γ(G) and upper domination number Γ(G) are respectively the minimum and maximum cardinalities taken over all minimal dominating sets of G. The independent domination number i(G) and the independence number β(G) are respectively the minimum and maximum cardinalities taken over all maximal independent sets of vertices of G.A variety of inequalities involving these quantities are established and sufficient conditions for the equality of the three upper parameters are given. In particular a conjecture of Hoyler and Cockayne 9], namely , is proved. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|