Opuscula Math. 29, no. 2 (2009), 165-175
http://dx.doi.org/10.7494/OpMath.2009.29.2.165

Opuscula Mathematica

# On the diameter of dot-critical graphs

Doost Ali Mojdeh
Somayeh Mirzamani

Abstract. A graph G is $$k$$-dot-critical (totaly $$k$$-dot-critical) if $$G$$ is dot-critical (totaly dot-critical) and the domination number is $$k$$. In the paper [T. Burtona, D. P. Sumner, Domination dot-critical graphs, Discrete Math, 306 (2006), 11-18] the following question is posed: What are the best bounds for the diameter of a $$k$$-dot-critical graph and a totally $$k$$-dot-critical graph $$G$$ with no critical vertices for $$k \geq 4$$? We find the best bound for the diameter of a $$k$$-dot-critical graph, where $$k \in\{4,5,6\}$$ and we give a family of $$k$$-dot-critical graphs (with no critical vertices) with sharp diameter $$2k-3$$ for even $$k \geq 4$$.

Keywords: dot-critical graph, diameter, .

Mathematics Subject Classification: 05C69.

Full text (pdf)

• Doost Ali Mojdeh
• Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, IRI
• Department of Mathematics, University of Mazandaran, Babolsar, IRI, P.O. Box 47416-1467
• Somayeh Mirzamani
• Department of Mathematics, University of Mazandaran, Babolsar, IRI, P.O. Box 47416-1467
• Revised: 2009-02-02.
• Accepted: 2009-04-22.