On the diameter of dot-critical graphs

• Autorzy: Mojdeh D. A. , Mirzamani S.
• Języki publikacji: EN

Abstrakty

EN

A graph G is k-dot-critical (totally k-dot-critical) if G is dot-critical (totally 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 ≥ 4? We find the best bound for the diameter of a k-dot-critical graph, where k ∈ {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 ≥ 4.

Słowa kluczowe

EN

dot-critical graph; domination; diameter

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2009
• Tom: Vol. 29, no. 2
• Strony: 165--175
• Opis fizyczny: Bibliogr. 6 poz., rys.

Twórcy

autor

Mojdeh D. A.

autor

Mirzamani S.

• Institute for Studies in Theoretical Physics and Mathematics (IPM) Tehran, IRI Department of Mathematics University of Mazandaran Babolsar, IRI, P.O. Box 47416-1467,

Bibliografia

• [1] R.C. Brigham, P.Z. Chinn, R.D. Dutton, A study of vertex domination critical graphs, Technical Report, University of Central Florida, 1984.
• [2] R.C. Brigham, T.W. Hanaynes, M.A. Henning, D.F. Rall, Bicritical domination, Discrete Mathematics 305 (2005), 18-32.
• [3] T.A. Burton, Domination dot-critical graphs, Ph.D. Dissertation, University of South Carolina, 2001.
• [4] T.A. Burton, D.P. Sumner, Domination dot-critical graphs, Discrete Mathematics 306 (2006), 11-18.
• [5] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of Domination in Graphs, Marcel Dekker, Inc., NewYork, 1998.
• [6] D.P. Sumner, P. Blitch, Domination critical graphs, JCT Ser. B 34 (1983), 65-76.