# Some recent results on domination in graphs

Discussiones Mathematicae Graph Theory (2006)

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

## Access Full Article

top## Abstract

top## How to cite

topMichael 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] 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] 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] 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] 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. Zbl1071.05060
- [6] N. Ananchuen and M.D. Plummer, Matchings in 3-vertex-critical graphs: the odd case, 2005, (submitted). Zbl1071.05060
- [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] 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. Zbl0658.05042
- [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] M. Cropper, D. Greenwell, A.J.W. Hilton and A. Kostochka, The domination number of cubic Hamiltonian graphs, (2005), (submitted). Zbl1101.05046
- [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] 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] 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] O. Favaron, On k-factor-critical graphs, Discuss. Math. Graph Theory 16 (1996) 41-51, doi: 10.7151/dmgt.1022. Zbl0865.05061
- [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] 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] 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] 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. Zbl0820.05038
- [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] 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] 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] 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). Zbl1179.05083
- [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. Zbl0911.05049
- [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] 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. Zbl0862.05032
- [31] S. Norine and R. Thomas, Generating bricks, preprint, 2005. Zbl1123.05077
- [32] S. Norine and R. Thomas, Minimal bricks, J. Combin. Theory (B) (2005), (to appear). Zbl1092.05056
- [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. Zbl0857.05052
- [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] 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 ?

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