On the codomination number of a graph

• Harary, Frank ^[1] ; Haynes, Teresa W. ^[2] ; Lewinter, Martin ^[3]
  1. [1] New Mexico State University

     New Mexico State University

     Estados Unidos

     
  2. [2] East Tennessee State University

     East Tennessee State University

     Estados Unidos

     
  3. [3] State University of New York

     State University of New York

     City of Albany, Estados Unidos

     

  Mostrar afiliaciones +
• Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 12, Nº. 2, 1993, págs. 149-153
• Idioma: inglés
• DOI: 10.22199/S07160917.1993.0002.00005
• Enlaces
  • Texto completo
• Resumen

  • 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.

• Referencias bibliográficas
  • Citas [1] Akiyama, J.; Harary F.: A graph and its complement with specified properties VII: A survey. G. Chartrand, ed., The Theory and...
  • [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.,...
  • [12] Jaeger, F,; Payan, C.: Relations du type Nordhaus-Gaddum pour le nombre d'absorption d'un graph simple. C. R. Acad. Sci. Paris,...
  • [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.