Inequality of Nordhaus-Gaddum Type for Total Outer-connected Domination in Graphs  

作　　者：Hong Xing JIANG Li Ying KANG 

机构地区：[1]College of Mathematics and Information Science, Wenzhou University, Wenzhou 325000, P. R. China [2]Department of Mathematics, Shanghai University, Shanghai 200444, P. R. China

出　　处：《Acta Mathematica Sinica,English Series》2011年第3期607-616,共10页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China （Grant Nos. 60773078, 10971131） and Shanghai Leading Academic Discipline Project （Grant No. S30104） Thank the referees sincerely for all of the helpful suggestions.

摘　　要：A set S of vertices in a graph G = （V, E） without isolated vertices is a total outer-connected dominating set （TCDS） of G if S is a total dominating set of G and G[V - S] is connected. The total outer-connected domination number of G, denoted by γtc（G）, is the minimum cardinality of a TCDS of G. For an arbitrary graph without isolated vertices, we obtain the upper and lower bounds on γtc（G） ＋ γytc（G）, and characterize the extremal graphs achieving these bounds.A set S of vertices in a graph G = （V, E） without isolated vertices is a total outer-connected dominating set （TCDS） of G if S is a total dominating set of G and G[V - S] is connected. The total outer-connected domination number of G, denoted by γtc（G）, is the minimum cardinality of a TCDS of G. For an arbitrary graph without isolated vertices, we obtain the upper and lower bounds on γtc（G） ＋ γytc（G）, and characterize the extremal graphs achieving these bounds.

关 键 词：GRAPH domination number total outer-connected domination Nordhaus-Gaddum inequality 

分 类 号：O178[理学—数学] TP311.13[理学—基础数学]