|
|||||
|
|
The diameter of total domination vertex critical graphs |
|
| Authors: | Wayne Goddard Teresa W. Haynes Lucas C. van der Merwe |
| Affiliation: | a Department of Computer Science, University of KwaZulu-Natal, Durban 4041, South Africa b Department of Mathematics, East Tennessee State University, Johnson City, TN 37614-0002, USA c School of Mathematics, Statistics, & Information Technology, University of KwaZulu-Natal, Pietermaritzburg 3209, South Africa d Department of Mathematics, University of Tennessee in Chattanooga, Chattanooga, TN 37403, USA |
| Abstract: | A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G-v is less than the total domination number of G. These graphs we call γt-critical. If such a graph G has total domination number k, we call it k-γt-critical. We characterize the connected graphs with minimum degree one that are γt-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γt-critical graph for k?8 and provide an example which shows that the maximum diameter is in general at least 5k/3-O(1). |
| Keywords: | 05C69 |
| 本文献已被 ScienceDirect 等数据库收录！ | |