Graphs with Diameter 2 and Large Total Domination Number
- PDF / 265,841 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 186 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Graphs with Diameter 2 and Large Total Domination Number Artu¯ras Dubickas1 Received: 26 November 2019 / Revised: 14 May 2020 / Accepted: 22 October 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract In this paper we show that for each sufficiently large n there exist graphs G of order n and diameter 2 whose total domination number ct ðGÞ is greater than pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi pffiffiffi ð3n log nÞ=8 n. On the other hand, it is shown that the total domination number of a graph of order n > 3 and diameter 2 is always less than pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi pffiffiffiffiffiffiffiffi ðn log nÞ=2 þ n=2. Keywords Graphs with diameter 2 Total domination number Random graph
Mathematics Subject Classification Primary 05C69 Secondary 05C80
1 Introduction Let G be a simple connected graph with n vertices. A vertex of G has degree g if it is adjacent to exactly g vertices of G. By dðGÞ we denote the minimum degree among all vertices of G. Let ct ðGÞ be the total domination number of G, that is, the minimal cardinality of a (not necessarily unique) set of vertices T such that every vertex of G (including those in T) is adjacent to a vertex in T. This concept was first introduced by Cockayne, Dawes and Hedetniemi in [4] and studied extensively afterwards. A recent book of Henning and Yeo [12] contains many references on this subject. There are also variations of this concept like weak and strong total domination [1], total k-domination (when each vertex of G has at least k neighbors in T) [2], a-total domination [3, 9], global domination [6], secure total & Artu¯ras Dubickas [email protected] 1
Institute of Mathematics, Faculty of Mathematics and Informatics, Vilnius University, Naugarduko 24, 03225 Vilnius, Lithuania
123
Graphs and Combinatorics
domination [7, 13], m-eternal total domination [14], signed total Roman domination [15], disjunctive total domination [17], etc. An upper bound for the total domination number of a graph G in terms of n and dðGÞ is given in [10, Theorem 3]: n 1 1 nð1 þ log dðGÞÞ : ct ðGÞ 6 1 þ þ ... þ 6 ð1Þ dðGÞ 2 dðGÞ dðGÞ Clearly, for graphs G of diameter 2 we also have ct ðGÞ 6 1 þ dðGÞ;
ð2Þ
since one can simply take T as a vertex with minimal degree and all dðGÞ vertices that are adjacent to it (see [5, Theorem 1]). From (1) and (2) it follows that Theorem 1 For every n > 3 and every connected graph G with n vertices and diameter 2 we have rffiffiffiffiffiffiffiffiffiffiffiffiffi rffiffiffi n log n n ð3Þ ct ðGÞ\ þ : 2 2
A slightly weaker inequality ct ðGÞ 6 1 þ
pffiffiffiffiffiffiffiffiffiffiffiffiffi n log n
has been established in [5, Theorem 4]. One can verify that the difference pffiffiffiffiffiffiffiffiffiffiffiffiffi pffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi pffiffiffiffiffiffiffiffi 1 þ n log n ðn log nÞ=2 n=2 is positive for each integer n > 3. (In fact, the smallest value for it occurs at n ¼ 35 and equals 0:839651. . ..) Also, in [5, Theorem 5] it was shown that for any e [ 0 there exists n0 ðeÞ such that for each even n > n0 ðeÞ there are graphs G of order n and diameter 2 satisfying pffiffiffiffiffiffiffiffiffiffiffiffiffi 1 ð4Þ n log n: e c
Data Loading...
