The Connectivity Of Domination Dot-Critical Graphs With No Critical Vertices

Michitaka Furuya

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 4, page 683-690
  • ISSN: 2083-5892

Abstract

top
An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and k(G) = 1. In this paper, we refine their result and construct for integers k ≥ 4 and l ≥ 1 infinitely many k-dot-critical graphs G with no critical vertices, k(G) = 1 and λ(G) = l. Furthermore, we prove that every 3-dot- critical graph with no critical vertices is 3-connected, and it is best possible.

How to cite

top

Michitaka Furuya. "The Connectivity Of Domination Dot-Critical Graphs With No Critical Vertices." Discussiones Mathematicae Graph Theory 34.4 (2014): 683-690. <http://eudml.org/doc/269821>.

@article{MichitakaFuruya2014,
abstract = {An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and k(G) = 1. In this paper, we refine their result and construct for integers k ≥ 4 and l ≥ 1 infinitely many k-dot-critical graphs G with no critical vertices, k(G) = 1 and λ(G) = l. Furthermore, we prove that every 3-dot- critical graph with no critical vertices is 3-connected, and it is best possible.},
author = {Michitaka Furuya},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dot-critical graph; critical vertex; connectivity.; connectivity},
language = {eng},
number = {4},
pages = {683-690},
title = {The Connectivity Of Domination Dot-Critical Graphs With No Critical Vertices},
url = {http://eudml.org/doc/269821},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Michitaka Furuya
TI - The Connectivity Of Domination Dot-Critical Graphs With No Critical Vertices
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 4
SP - 683
EP - 690
AB - An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and k(G) = 1. In this paper, we refine their result and construct for integers k ≥ 4 and l ≥ 1 infinitely many k-dot-critical graphs G with no critical vertices, k(G) = 1 and λ(G) = l. Furthermore, we prove that every 3-dot- critical graph with no critical vertices is 3-connected, and it is best possible.
LA - eng
KW - dot-critical graph; critical vertex; connectivity.; connectivity
UR - http://eudml.org/doc/269821
ER -

References

top
  1. [1] T. Burton and D.P. Sumner, Domination dot-critical graphs, Discrete Math. 306 (2006) 11-18. doi:10.1016/j.disc.2005.06.029 Zbl1085.05047
  2. [2] X. Chen and W.C. Shiu, A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745. doi:10.1016/j.dam.2009.07.014 Zbl1227.05204
  3. [3] R. Diestel, Graph Theory 4th Edition (Verlag, Heidelberg, Springer, 2010). 
  4. [4] M. Furuya and M. Takatou, Upper bound on the diameter of a domination dot- critical graph, Graphs Combin. 29 (2013) 79-85. doi:10.1007/s00373-011-1095-1 Zbl1258.05093
  5. [5] D.A. Mojdeh and S. Mirzamani, On the diameter of dot-critical graphs, Opuscula Math. 29 (2009) 165-175. Zbl1204.05070
  6. [6] N.J. Rad, On the diameter of a domination dot-critical graph, Discrete Appl. Math. 157 (2009) 1647-1649. doi:10.1016/j.dam.2008.10.015 Zbl1182.05066

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.