Paired Domination Vertex Critical Graphs |
| |
Authors: | Xinmin Hou Michelle Edwards |
| |
Institution: | (1) Department of Mathematics, University of Science and Technology of China, Hefei, Anhui, 230026, China;(2) Department of Mathematics and Statistics, University of Victoria, Victoria, BC, Canada, V8W 3R4 |
| |
Abstract: | Let γ
pr
(G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ
pr
(G – v) < γ
pr
(G). We call these graphs γ
pr
-critical. In this paper, we present a method of constructing γ
pr
-critical graphs from smaller ones. Moreover, we show that the diameter of a γ
pr
-critical graph is at most and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt The diameter of paired-domination
vertex critical graphs, Czechoslovak Math. J., to appear].
Xinmin Hou: Research supported by NNSF of China (No.10701068 and No.10671191). |
| |
Keywords: | Paired domination Critical Graph Diameter |
本文献已被 SpringerLink 等数据库收录! |
|