Some recent results on domination in graphs

Michael D. Plummer

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 3, page 457-474
  • ISSN: 2083-5892

Abstract

top
In this paper, we survey some new results in four areas of domination in graphs, namely: (1) the toughness and matching structure of graphs having domination number 3 and which are "critical" in the sense that if one adds any missing edge, the domination number falls to 2; (2) the matching structure of graphs having domination number 3 and which are "critical" in the sense that if one deletes any vertex, the domination number falls to 2; (3) upper bounds on the domination number of cubic graphs; and (4) upper bounds on the domination number of graphs embedded in surfaces.

How to cite

top

Michael D. Plummer. "Some recent results on domination in graphs." Discussiones Mathematicae Graph Theory 26.3 (2006): 457-474. <http://eudml.org/doc/270200>.

@article{MichaelD2006,
abstract = { In this paper, we survey some new results in four areas of domination in graphs, namely: (1) the toughness and matching structure of graphs having domination number 3 and which are "critical" in the sense that if one adds any missing edge, the domination number falls to 2; (2) the matching structure of graphs having domination number 3 and which are "critical" in the sense that if one deletes any vertex, the domination number falls to 2; (3) upper bounds on the domination number of cubic graphs; and (4) upper bounds on the domination number of graphs embedded in surfaces. },
author = {Michael D. Plummer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; matching; toughness; cubic graph; triangulation; genus; cubic graphs},
language = {eng},
number = {3},
pages = {457-474},
title = {Some recent results on domination in graphs},
url = {http://eudml.org/doc/270200},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Michael D. Plummer
TI - Some recent results on domination in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 3
SP - 457
EP - 474
AB - In this paper, we survey some new results in four areas of domination in graphs, namely: (1) the toughness and matching structure of graphs having domination number 3 and which are "critical" in the sense that if one adds any missing edge, the domination number falls to 2; (2) the matching structure of graphs having domination number 3 and which are "critical" in the sense that if one deletes any vertex, the domination number falls to 2; (3) upper bounds on the domination number of cubic graphs; and (4) upper bounds on the domination number of graphs embedded in surfaces.
LA - eng
KW - domination; matching; toughness; cubic graph; triangulation; genus; cubic graphs
UR - http://eudml.org/doc/270200
ER -

References

top
  1. [1] N. Ananchuen and M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs, Discrete Math. 272 (2003) 5-15, doi: 10.1016/S0012-365X(03)00179-1. Zbl1029.05110
  2. [2] N. Ananchuen and M.D. Plummer, Some results related to the toughness of 3-domination critical graphs, II, Utilitas Math. (2006), (to appear). Zbl1118.05069
  3. [3] N. Ananchuen and M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13, doi: 10.1016/S0012-365X(03)00243-7. Zbl1033.05076
  4. [4] N. Ananchuen and M.D. Plummer, 3-factor-criticality in domination critical graphs, (2005), (submitted). 
  5. [5] N. Ananchuen and M.D. Plummer, Matchings in 3-vertex-critical graphs: the even case, Networks 45 (2005) 210-213, doi: 10.1002/net.20065. Zbl1071.05060
  6. [6] N. Ananchuen and M.D. Plummer, Matchings in 3-vertex-critical graphs: the odd case, 2005, (submitted). Zbl1071.05060
  7. [7] N. Ananchuen and M.D. Plummer, On the connectivity and matchings in 3-vertex-critical claw-free graphs, Utilitas Math. (2006), (to appear). Zbl1103.05064
  8. [8] R.C. Brigham, P.Z. Chinn and R.D. Dutton, A study of vertex domination critical graphs (Dept. of Math. Tech. Report M-2, Univ. of Central Florida, 1984). 
  9. [9] R.C. Brigham, P.Z. Chinn and R.D. Dutton, Vertex domination-critical graphs, Networks 18 (1988) 173-179, doi: 10.1002/net.3230180304. Zbl0658.05042
  10. [10] Y. Chen, F. Tian and B. Wei, The 3-domination-critical graphs with toughness one, Utilitas Math. 61 (2002) 239-253. Zbl0992.05056
  11. [11] M. Cropper, D. Greenwell, A.J.W. Hilton and A. Kostochka, The domination number of cubic Hamiltonian graphs, (2005), (submitted). Zbl1101.05046
  12. [12] M.H. de Carvalho, C.L. Lucchesi and U.S.R. Murty, On a conjecture of Lovász concerning bricks. I. The characteristic of a matching covered graph, J. Combin. Theory (B) 85 (2002) 94-136, doi: 10.1006/jctb.2001.2091. Zbl1024.05069
  13. [13] M.H. de Carvalho, C.L. Lucchesi and U.S.R. Murty, On a conjecture of Lovász concerning bricks. II. Bricks of finite characteristic, J. Combin. Theory (B) 85 (2002) 137-180, doi: 10.1006/jctb.2001.2092. Zbl1024.05070
  14. [14] J. Edmonds, L. Lovász and W.R. Pulleyblank, Brick decompositions and the matching rank of graphs, Combinatorica 2 (1982) 247-274, doi: 10.1007/BF02579233. Zbl0521.05035
  15. [15] O. Favaron, On k-factor-critical graphs, Discuss. Math. Graph Theory 16 (1996) 41-51, doi: 10.7151/dmgt.1022. Zbl0865.05061
  16. [16] O. Favaron, E. Flandrin and Z. Ryjácek, Factor-criticality and matching extension in DCT-graphs, Discuss. Math. Graph Theory 17 (1997) 271-278, doi: 10.7151/dmgt.1054. Zbl0907.05040
  17. [17] J. Fiedler, J. Huneke, R. Richter and N. Robertson, Computing the orientable genus of projective graphs, J. Graph Theory 20 (1995) 297-308, doi: 10.1002/jgt.3190200305. Zbl0837.05051
  18. [18] E. Flandrin, F. Tian, B. Wei and L. Zhang, Some properties of 3-domination-critical graphs, Discrete Math. 205 (1999) 65-76, doi: 10.1016/S0012-365X(99)00038-2. Zbl0947.05059
  19. [19] J. Fulman, Domination in vertex and edge critical graphs (Manuscript, Harvard Univ., 1992). 
  20. [20] J. Fulman, D. Hanson and G. MacGillivray, Vertex domination-critical graphs, Networks 25 (1995) 41-43, doi: 10.1002/net.3230250203. Zbl0820.05038
  21. [21] M. Garey and D. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W.H. Freeman and Co. (San Francisco, 1979) 190. Zbl0411.68039
  22. [22] K. Kawarabayashi, A. Saito and M.D. Plummer, Domination in a graph with a 2-factor, J. Graph Theory (2006), (to appear), (Early view online at www.interscience.wiley.com, DOI 10.10021 jgt. 20142). Zbl1118.05075
  23. [23] A.V. Kostochka and B.Y. Stodolsky, On domination in connected cubic graphs, Communication: Discrete Math. 304 (2005) 45-50, doi: 10.1016/j.disc.2005.07.005. Zbl1077.05078
  24. [24] A.V. Kostochka and B.Y. Stodolsky, personal communication, November, 2005. 
  25. [25] A.V. Kostochka and B.Y. Stodolsky, An upper bound on the domination number of n-vertex connected cubic graphs, December, 2005, (submitted). Zbl1179.05083
  26. [26] M. Las Vergnas, A note on matchings in graphs, Colloque sur la Théorie des Graphes (Paris, 1974) Cahiers Centre Études Rech. Opér. 17 (1975) 257-260. 
  27. [27] G. Liu and Q. Yu, On n-edge-deletable and n-critical graphs, Bull. Inst. Combin. Appl. 24 (1998) 65-72. Zbl0911.05049
  28. [28] L. Lovász, Matching structure and the matching lattice, J. Combin. Theory (B) 43 (1987) 187-222, doi: 10.1016/0095-8956(87)90021-9. Zbl0659.05081
  29. [29] L. Lovász and M.D. Plummer, Matching Theory, Ann. Discrete Math. 29 (North-Holland, Amsterdam, 1986). 
  30. [30] L. Matheson and R. Tarjan, Dominating sets in planar graphs, European J. Combin. 17 (1996) 565-568, doi: 10.1006/eujc.1996.0048. Zbl0862.05032
  31. [31] S. Norine and R. Thomas, Generating bricks, preprint, 2005. Zbl1123.05077
  32. [32] S. Norine and R. Thomas, Minimal bricks, J. Combin. Theory (B) (2005), (to appear). Zbl1092.05056
  33. [33] M.D. Plummer and X. Zha, On certain spanning subgraphs of embeddings with applications to domination, 2005, (submitted). 
  34. [34] B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295, doi: 10.1017/S0963548300002042. Zbl0857.05052
  35. [35] D.P. Sumner, 1-factors and anti-factor sets, J. London Math. Soc. 13 (1976) 351-359, doi: 10.1112/jlms/s2-13.2.351. Zbl0338.05118
  36. [36] D.P. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory (B) 34 (1983) 65-76, doi: 10.1016/0095-8956(83)90007-2. Zbl0512.05055

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.