阶数极大的临界全控制图

Total domination critical graphs with maximal order

称一个没有孤立点的图G为临界全控制图,如果G满足对于任何一个不与悬挂点相邻的顶点v,G-v的全控制数都小于G的全控制数.如果G的全控制数记为γt,则称这样的临界全控制图G为γt-临界的.如果G是γt-临界的,且阶数为n,则n≤△(G)(γt(G)-1)+1,其中△(G)是G的最大度.本文将证明对γt=3,这个阶数的上界是紧的,并给出所有满足n≤△(G)(γt(G)-1)+1的3-γt-临界图.

A graph G without isolated vertices is total domination vertex critical, if for any vertex v of G that is not adjacent to a pendant vertex, the total domination number of G-v is less than the total domination number of G. We call these graphs γt-critical. If G is a γt-critical graph of order n, then it can be shown that n≤△（G）（γt（G）-1）＋1, where △（G） is the maximum degree of G. In this paper, we characterize the graphs in the case n≤△（G）（γt（G）-1）＋1 with γt（G） = 3.