On the codomination number of a graph
DOI:
https://doi.org/10.22199/S07160917.1993.0002.00005Keywords:
Codominación, GráficoAbstract
Given a graph G = (V, E), set S ? V is a dominating set if each node of V - S is adjacent to at least one node in S. The domination number of G is the smallest size of a dominating set and the codomination number is the domination number of its complement. We determine the codomination number of a graph having diameter at least three. Further we explore the effects of this result on the open problem of characterizing graphs having equal domination and codomination numbers.
References
[1] Akiyama, J.; Harary F.: A graph and its complement with specified properties VII: A survey. G. Chartrand, ed., The Theory and Applications of Graphs. Wiley, New York, (1981), 1-12.
[2] Brigham, R. C.; Carrington, J. R.: Factor domination. Congr. Numer., 83 (1991), 201-211.
[3] Brigham, R. C.; Carrington, J. R.: Global domination of simple factors. Congr. Numer., 88 (1992), 161-167.
[4] Brigham, R.C.; Chinn, P.Z.; Dutton, R.D.: Vertex domination-critical graphs. Networks 18 (1988), 173-179.
[5] Brigham, R.C.; Dutton, R.D.: Factor domination m graphs. Discrete Math., 86 (1990), 127-136.
[6] Dunbar, J.: Laskar, R.; Monroe, T.: Global irredundant sets in graphs. Congr. Numer., 85 (1991), 65-72.
[7] Dunbar, J.: Laskar, R.; Monroe, T.: Some global parameters of graphs. Congr. Numer., 89 (1992), 187-191.
[8] Harary, F.: Graph Theory. Addison- Wesley, Reading, 1969.
[9] Harary, F.; Haynes T.W.: Nordhaus-Gaddum inequalities on graph domination. Networks, to appear.
[10] Harary, F.; Robinson, R.W.: The diameter of a graph and its complement. Amer. Math. Monthly, 92 (1985), 211-212.
[11] Hedetniemi, S.T.; Laskar, R.: Bibliography on domination in graphs and some basic definitions of domination parametes. Discrete Math., 86 (1990), 257-277.
[12] Jaeger, F,; Payan, C.: Relations du type Nordhaus-Gaddum pour le nombre d'absorption d'un graph simple. C. R. Acad. Sci. Paris, A 274 (1972), 728-730.
[13] Laskar, R.; Peters, K.: Vertex and edge domination parameters in graphs. Congr. Numer., 48 (1985), 291-305.
[14] Lewinter, M.: The diameter of the complement of a regular graph. Congr. Numer., 64 (1988) 157-158.
[15] Rall, D.: Dominating a graph and its compement. Congr. Numer., 64 (1988) 157-158.
[16] Sampathkumar, E.: The global domination number of a graph. J. Math. Phy. Sci., 23 (1989) 377-385.
[2] Brigham, R. C.; Carrington, J. R.: Factor domination. Congr. Numer., 83 (1991), 201-211.
[3] Brigham, R. C.; Carrington, J. R.: Global domination of simple factors. Congr. Numer., 88 (1992), 161-167.
[4] Brigham, R.C.; Chinn, P.Z.; Dutton, R.D.: Vertex domination-critical graphs. Networks 18 (1988), 173-179.
[5] Brigham, R.C.; Dutton, R.D.: Factor domination m graphs. Discrete Math., 86 (1990), 127-136.
[6] Dunbar, J.: Laskar, R.; Monroe, T.: Global irredundant sets in graphs. Congr. Numer., 85 (1991), 65-72.
[7] Dunbar, J.: Laskar, R.; Monroe, T.: Some global parameters of graphs. Congr. Numer., 89 (1992), 187-191.
[8] Harary, F.: Graph Theory. Addison- Wesley, Reading, 1969.
[9] Harary, F.; Haynes T.W.: Nordhaus-Gaddum inequalities on graph domination. Networks, to appear.
[10] Harary, F.; Robinson, R.W.: The diameter of a graph and its complement. Amer. Math. Monthly, 92 (1985), 211-212.
[11] Hedetniemi, S.T.; Laskar, R.: Bibliography on domination in graphs and some basic definitions of domination parametes. Discrete Math., 86 (1990), 257-277.
[12] Jaeger, F,; Payan, C.: Relations du type Nordhaus-Gaddum pour le nombre d'absorption d'un graph simple. C. R. Acad. Sci. Paris, A 274 (1972), 728-730.
[13] Laskar, R.; Peters, K.: Vertex and edge domination parameters in graphs. Congr. Numer., 48 (1985), 291-305.
[14] Lewinter, M.: The diameter of the complement of a regular graph. Congr. Numer., 64 (1988) 157-158.
[15] Rall, D.: Dominating a graph and its compement. Congr. Numer., 64 (1988) 157-158.
[16] Sampathkumar, E.: The global domination number of a graph. J. Math. Phy. Sci., 23 (1989) 377-385.
Published
2018-04-03
How to Cite
[1]
F. Harary, T. W. Haynes, and M. Lewinter, “On the codomination number of a graph”, Proyecciones (Antofagasta, On line), vol. 12, no. 2, pp. 149-153, Apr. 2018.
Issue
Section
Artículos
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
