Download PDF - Some recent results on domination in graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Some recent results on domination in graphs

Authors 1

Affiliations

  1. Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37240, USA

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.

Keywords

ENG
domination, matching, toughness, cubic graph, triangulation, genus

Bibliography

  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.
  2. N. Ananchuen and M.D. Plummer, Some results related to the toughness of 3-domination critical graphs, II, Utilitas Math. (2006), (to appear).
  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.
  4. N. Ananchuen and M.D. Plummer, 3-factor-criticality in domination critical graphs, (2005), (submitted).
  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.
  6. N. Ananchuen and M.D. Plummer, Matchings in 3-vertex-critical graphs: the odd case, 2005, (submitted).
  7. N. Ananchuen and M.D. Plummer, On the connectivity and matchings in 3-vertex-critical claw-free graphs, Utilitas Math. (2006), (to appear).
  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. R.C. Brigham, P.Z. Chinn and R.D. Dutton, Vertex domination-critical graphs, Networks 18 (1988) 173-179, doi: 10.1002/net.3230180304.
  10. Y. Chen, F. Tian and B. Wei, The 3-domination-critical graphs with toughness one, Utilitas Math. 61 (2002) 239-253.
  11. M. Cropper, D. Greenwell, A.J.W. Hilton and A. Kostochka, The domination number of cubic Hamiltonian graphs, (2005), (submitted).
  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.
  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.
  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.
  15. O. Favaron, On k-factor-critical graphs, Discuss. Math. Graph Theory 16 (1996) 41-51, doi: 10.7151/dmgt.1022.
  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.
  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.
  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.
  19. J. Fulman, Domination in vertex and edge critical graphs (Manuscript, Harvard Univ., 1992).
  20. J. Fulman, D. Hanson and G. MacGillivray, Vertex domination-critical graphs, Networks 25 (1995) 41-43, doi: 10.1002/net.3230250203.
  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.
  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).
  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.
  24. A.V. Kostochka and B.Y. Stodolsky, personal communication, November, 2005.
  25. A.V. Kostochka and B.Y. Stodolsky, An upper bound on the domination number of n-vertex connected cubic graphs, December, 2005, (submitted).
  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. G. Liu and Q. Yu, On n-edge-deletable and n-critical graphs, Bull. Inst. Combin. Appl. 24 (1998) 65-72.
  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.
  29. L. Lovász and M.D. Plummer, Matching Theory, Ann. Discrete Math. 29 (North-Holland, Amsterdam, 1986).
  30. L. Matheson and R. Tarjan, Dominating sets in planar graphs, European J. Combin. 17 (1996) 565-568, doi: 10.1006/eujc.1996.0048.
  31. S. Norine and R. Thomas, Generating bricks, preprint, 2005.
  32. S. Norine and R. Thomas, Minimal bricks, J. Combin. Theory (B) (2005), (to appear).
  33. M.D. Plummer and X. Zha, On certain spanning subgraphs of embeddings with applications to domination, 2005, (submitted).
  34. B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295, doi: 10.1017/S0963548300002042.
  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.
  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.
Discussiones Mathematicae Graph Theory
2006/26/3
Export to PBN, Opens in new tab
Pages:
457-474
Main language of publication
English
Received
2005-11-23
Published
2006

DOI: 10.7151/dmgt.1338

Exact and natural sciences