The total domination number γt(G) of a graph G is the minimum cardinality of a set S of vertices, so that every vertex of G is adjacent to a vertex in S. In this article, we determine an optimal upper bound on the total domination number of a graph with diameter 2. We show that for every graph G on n vertices with diameter 2, γt(G)≤1+nln(n). This bound is optimal in the sense that given any ε>0, there exist graphs G with diameter 2 of all sufficiently large even orders n such that γt(G)>(14+ε)nln(n).
Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-17088 |
Date | 01 January 2014 |
Creators | Desormeaux, Wyatt J., Haynes, Teresa W., Henning, Michael A., Yeo, Anders |
Publisher | Digital Commons @ East Tennessee State University |
Source Sets | East Tennessee State University |
Detected Language | English |
Type | text |
Source | ETSU Faculty Works |
Page generated in 0.0022 seconds