A constructive characterization of total domination vertex critical graphs |
| |
Authors: | Chunxiang Wang Zhiquan Hu |
| |
Affiliation: | Department of Mathematics, Huazhong Normal University, Wuhan, 430079, PR China |
| |
Abstract: | Let G be a graph of order n and maximum degree Δ(G) and let γt(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the 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. We call these graphs γt-critical. For any γt-critical graph G, it can be shown that n≤Δ(G)(γt(G)−1)+1. In this paper, we prove that: Let G be a connected γt-critical graph of order n (n≥3), then n=Δ(G)(γt(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A. |
| |
Keywords: | Total domination set Total domination number Vertex critical graphs Cayley graphs Corona |
本文献已被 ScienceDirect 等数据库收录! |
|