×

The diameter of domination \(k\)-critical graphs. (English) Zbl 0807.05042

A graph \(G\) is called domination \(k\)-critical, if it has the domination number \(k\) and after deleting an arbitrary edge of \(G\) a graph \(G'\) with domination number less than \(k\) is obtained. The paper studies diameters of such graphs. For \(k\geq 2\) the upper bound for the domination number of a domination \(k\)-critical graph is found, namely \(2k-2\). It is proved that there exists such a graph with diameter \(\bigl\lfloor{3\over 2} k- 1\bigr\rfloor\). For \(k= 4\) the above mentioned upper bound is 5.

MSC:

05C35 Extremal problems in graph theory
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bauer, Discrete Math. 47 pp 153– (1983)
[2] Brigham, Networks 18 pp 173– (1988)
[3] Sumner, Discrete Math. 86 pp 33– (1990)
[4] Sumner, J. Combinat. Theory Ser. B 34 pp 65– (1983)
[5] and , Cutpoints in domination critical graphs. Preprint.
[6] Wojcicka, J. Graph Theory 14 pp 205– (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.