广义de Bruijn和Kautz有向图的距离控制数

对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?)．图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者．本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件．从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= ．在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= .     

5-正则图的全控制数的一个注记

设G是不含孤立点的图,S是G的一个顶点子集,若G的每一个顶点都与S中的某顶点邻接,则称S是G的全控制集.G的最小全控制集所含顶点的个数称为G的全控制数,记为γt(G).Thomasse和Yeo证明了若G是最小度至少为5的n阶连通图,则γt(G)≤17n/44.在5-正则图上改进了Thomasse和Yeo的结论,证明了若G是n阶5-正则图,则,γt(G)≤106n/275.     

图的符号星部分控制数

引入了图的符号星部分控制的概念.设G=(V,E)是一个简单连通图, M是V的一个子集.一个函数f:E→{-1,1}若满足∑e∈E(v)f(e)≥1对M中的每个顶点v都成立,则称f是图G的一个符号星部分控制函数,其中E(v)表示G中与v点相关连的边集.图G的符号星部分控制数定义为γM(85)(G)=min{∑e∈Ef(e)|f是G的符号星部分控制函数}.在本文中我们主要给出了一般图的符号星部分控制数的上界和下界,并确定了路、圈和完全图的符号星部分控制数的精确值.作为我们引入的这一新概念的一个应用,求出了完全图的符号星k控制数.     

立方图的对控制数

设G=(V,E)是一个简单图, 对任意的顶点子集合 $S\subseteq V$, G[S]表示图G中由S所导出的子图. 如果S是G的一个控制集并且G[S]包含至少一个完备匹配, 则称S是G的一个对控制集. G中对控制集的最少的顶点数称为$G$的对控制数, 记为γ_p(G). 该文证明了对任意有n点的连通立方图G, γ_p(G)≤3n/ 5.     

关于图的符号星控制数

设G=(V,E)是一个图,u∈V,则E(u)表示u点所关联的边集.一个函数f:E→{-1,1}如果满足■f(e)≥1对任意v∈V成立,则称f为图G的一个符号星控制函数,图G的符号星控制数定义为γ'_(ss)(G)=min{■f(e):f为图G的一个符号星控制函数}.给出了几类特殊图的符号星控制数,主要包含完全图,正则偶图和完全二部图.     

度为奇数的正则图的上负全控制数

f:v(G)→{一1,0,1}称为图G的负全控制函数,如果对任意点V∈V,均有f[v]≥1,其中 f[v]= ∑,f(u).如果对每个点v∈V,不存在负全控制函数g:V(G)→{-l,0,1),g≠f,满u∈N(v)足g(v)≤f(v),则称f是-个极小负全控制函数.图的上负全控制数F-t(G)=max{w(f)|f,是G的极小负全控制函数},其中w(f)=∑/v∈V(G)f(v).本文研究正则图的上负全控制数,证明了:令G是-个v∈V(G)n阶r-正则图.若r为奇数,则Γt-(G)＜＝r2 1/r2 2r-1n.     

图的双控制的一些新结果

图G=(V,E)的每个顶点控制它的闭邻域的每个顶点.S是一个顶点子集合,如果G的每一个顶点至少被S中的两个顶点控制,则称S是G的一个双控制集.把双控制集的最小基数称为双控制数,记为dd(G).本文探讨了双控制数和其它控制参数的一些新关系,推广了[1]的一些结果.并且给出了双控制数的Nordhaus-Gaddum类型的结果.     

图的符号星k控制数

引入了图的符号星k控制的概念.设G=（V,E）是一个图,一个函数f：E→{-1,＋1},如果∑e∈E[v]f（e）≥1对于至少k个顶点v∈V（G）成立,则称f为图G的一个符号星k控制函数,其中E（v）表示G中与v点相关联的边集.图G的符号星k控制数定义为γkss（G）=min{∑e∈Ef（e）｜f为图G的符号星k控制函数}.在本文中,我们主要给出了一般图的符号星k控制数的若干下界,推广了关于符号星控制的一个结果,并确定路和圈的符号星k控制数.     

几类图的符号控制

设G=(V,E)是一个图,一个函数f:V→{-1,+1}如果满足Σv∈N[υ]f(ν)≥1对于每个点u∈V成立,则称f为图G的一个符号控制函数,图G的符号控制数γs(G)定义为γs(G)=min{Σv∈vf(v)|f为图G的符号控制函数},类似地,可定义图G的上符号控制数Γs(G).研究了几类特殊图的符号控制问题,获得了完全l等部图和乘积图P_3×P_n的符号控制数,并确定了P_2×P_n和P_3×P_n的上符号控制数.     

弱罗马控制数与最小控制数相同的树

Henning M A等提出了图的弱罗马控制数(记为γ_r(G))的概念,给出了弱罗马控制数与最小控制数相同的图(即γ(G)=γ_r(G))的特征.树是无圈的连通图,相同条件下它除了满足上述的特征外,还具有自身的特点.运用递归法和指标函数法,刻画了弱罗马控制数与最小控制数相同的树(即γ(T)=γ_r(T))的特征.     

On graphs with equal domination and 2-domination numbers

Let G be a simple graph, and let p be a positive integer. A subset D⊆V(G) is a p-dominating set of the graph G, if every vertex v∈V(G)-D is adjacent to at least p vertices in D. The p-domination numberγ_p(G) is the minimum cardinality among the p-dominating sets of G. Note that the 1-domination number γ₁(G) is the usual domination numberγ(G). This definition immediately leads to the inequality γ(G)?γ₂(G).In this paper we present some sufficient as well as some necessary conditions for graphs G with the property that γ₂(G)=γ(G). In particular, we characterize all cactus graphs H with γ₂(H)=γ(H).     

Total [1,2]-domination in Graphs

A subset S ? V in a graph G = (V,E) is a total [1, 2]-set if, for every vertex \( \upsilon \in V, 1 \leq\mid N (\upsilon)\cap S\mid\leq \). The minimum cardinality of a total [1, 2]-set of G is called the total [1, 2]-domination number, denoted by γ_t[1,2](^G).We establish two sharp upper bounds on the total [1,2]-domination number of a graph G in terms of its order and minimum degree, and characterize the corresponding extremal graphs achieving these bounds. Moreover, we give some sufficient conditions for a graph without total [1, 2]-set and for a graph with the same total [1, 2]-domination number, [1, 2]-domination number and domination number.     

New results on 3-domination critical graphs

A graph G is said to be 3-domination critical if its domination number γ(G) = 3 and γ(G + e) = 2 for any edge e not contained in G. In this paper we first establish some structural properties of 3-domination critical graphs with diameter equal to 3. In particular, this allows us to characterize a special family of 3-domination critical graphs which contains those with minimum degree one. Moreover, we show that if the minimum degree of a 3-domination critical graph G is at least 3, then α(G) ≤ κ(G) + 1 or G is superconnected, where α(G) is the independence number and κ(G) is the vertex-connectivity of G.     

Some results related to the toughness of 3-domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k−1 vertices. The structure of k-γ-critical graphs remains far from completely understood, even in the special case when the domination number γ=3. In a 1983 paper, Sumner and Blitch proved a theorem which may regarded as a result related to the toughness of 3-γ-critical graphs which says that if S is any vertex cutset of such a graph, then G−S has at most |S|+1 components. In the present paper, we improve and extend this result considerably.     

Codiameters of 3-domination critical graphs with toughness more than one

A graph G is 3-domination-critical (3-critical, for short), if its domination number γ is 3 and the addition of any edge decreases γ by 1. In this paper, we show that every 3-critical graph with independence number 4 and minimum degree 3 is Hamilton-connected. Combining the result with those in [Y.J. Chen, F. Tian, B. Wei, Hamilton-connectivity of 3-domination critical graphs with α≤δ, Discrete Mathematics 271 (2003) 1-12; Y.J. Chen, F. Tian, Y.Q. Zhang, Hamilton-connectivity of 3-domination critical graphs with α=δ+2, European Journal of Combinatorics 23 (2002) 777-784; Y.J. Chen, T.C.E. Cheng, C.T. Ng, Hamilton-connectivity of 3-domination critical graphs with α=δ+1≥5, Discrete Mathematics 308 (2008) (in press)], we solve the following conjecture: a connected 3-critical graph G is Hamilton-connected if and only if τ(G)>1, where τ(G) is the toughness of G.     

Characterization of graphs with hall number 2

Hall's condition is a simple requirement that a graph G and list assignment L must satisfy if G is to have a proper L‐colouring. The Hall number of G is the smallest integer m such that whenever the lists on the vertices each has size at least m and Hall's condition is satisfied a proper L‐colouring exists. Hilton and P.D. Johnson introduced the parameter and showed that a graph has Hall number 1 if and only if every block is a clique. In this paper we give a forbidden‐induced‐subgraph characterization of graphs with Hall number 2. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 81–100, 2004