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.
- 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
- Received: 2007-09-02.
- Revised: 2009-02-02.
- Accepted: 2009-04-22.
