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 do...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.展开更多
The induced path number p（G） of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a path. Broere et hi. proved that if G is a graph o...The induced path number p（G） of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a path. Broere et hi. proved that if G is a graph of order n, then 〈 p（G） ＋ p（G） 〈3n/2] . In this paper,_we characterize [3n/2], improve the lower bound on p（G） ＋ p（G） by one when the graphs G for which p（G） -4- p（G） = 3n n is the square of an odd integer, and determine a best possible upper bound for p（G） ＋ p（G） when neither G nor G has isolated vertices.展开更多
Let the chromatic number of G, the edge chromatic number of G and thetotal chromatic number of G be denoted by x（G）, x<sub>1</sub>（G） and x<sub>2</sub>（G）, respectively. Forany simple gra...Let the chromatic number of G, the edge chromatic number of G and thetotal chromatic number of G be denoted by x（G）, x<sub>1</sub>（G） and x<sub>2</sub>（G）, respectively. Forany simple graph G of order p and its complement G, the following inequalities of theNordhaus-Gaddum class are obtained:（i）|2p<sup>1/2</sup>|-ε<sub>1</sub>≤x（G）+x<sub>1</sub>（G）≤2p-2 and 0≤x（G）·x<sub>1</sub>（G）≤（p-1）<sup>2</sup> for p≥2,（ii）|2p<sup>1/2</sup>|+ε<sub>1</sub>≤x（G）+x<sub>2</sub>（G）≤2p-1 and 0≤x（G）·x<sub>2</sub>（G）≤p（p-1） for p≥3,（iii）p≤x<sub>1</sub>（G）+x<sub>2</sub>（G）≤2p-1 and 0≤x<sub>1</sub>（G）·x<sub>2</sub>（G）≤p（p-1） for p≥3,where ε<sub>1</sub>=0, if p<sup>1/2</sup> is an odd integer, 1, otherwise,ε<sub>2</sub>=1, if p<sup>1/2</sup> is an even integer, 0, otherwise,and [x] denotes the ceiling of x. We also show that these bounds are sharp for everypositive integer p.展开更多
基金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.
文摘The induced path number p（G） of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a path. Broere et hi. proved that if G is a graph of order n, then 〈 p（G） ＋ p（G） 〈3n/2] . In this paper,_we characterize [3n/2], improve the lower bound on p（G） ＋ p（G） by one when the graphs G for which p（G） -4- p（G） = 3n n is the square of an odd integer, and determine a best possible upper bound for p（G） ＋ p（G） when neither G nor G has isolated vertices.
文摘Let the chromatic number of G, the edge chromatic number of G and thetotal chromatic number of G be denoted by x（G）, x<sub>1</sub>（G） and x<sub>2</sub>（G）, respectively. Forany simple graph G of order p and its complement G, the following inequalities of theNordhaus-Gaddum class are obtained:（i）|2p<sup>1/2</sup>|-ε<sub>1</sub>≤x（G）+x<sub>1</sub>（G）≤2p-2 and 0≤x（G）·x<sub>1</sub>（G）≤（p-1）<sup>2</sup> for p≥2,（ii）|2p<sup>1/2</sup>|+ε<sub>1</sub>≤x（G）+x<sub>2</sub>（G）≤2p-1 and 0≤x（G）·x<sub>2</sub>（G）≤p（p-1） for p≥3,（iii）p≤x<sub>1</sub>（G）+x<sub>2</sub>（G）≤2p-1 and 0≤x<sub>1</sub>（G）·x<sub>2</sub>（G）≤p（p-1） for p≥3,where ε<sub>1</sub>=0, if p<sup>1/2</sup> is an odd integer, 1, otherwise,ε<sub>2</sub>=1, if p<sup>1/2</sup> is an even integer, 0, otherwise,and [x] denotes the ceiling of x. We also show that these bounds are sharp for everypositive integer p.
