On the diameter of dot-critical graphs
Author(s) -
Doost Ali Mojdeh,
Somayeh Mirzamani
Publication year - 2009
Publication title -
opuscula mathematica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.481
H-Index - 16
eISSN - 2300-6919
pISSN - 1232-9274
DOI - 10.7494/opmath.2009.29.2.165
Subject(s) - mathematics , combinatorics , discrete mathematics
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\)
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom