A Note on the Bondage Number of a Graph

ＡＮｏｔｅｏｎｔｈｅＢｏｎｄａｇｅＮｕｍｂｅｒｏｆａＧｒａｐｈ￥ＬｉＹｕｑｉａｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＧｕａｎｇｚｈｏｕＴｅａｃｈｅｒ＇ｓＣｏｌｌｅｇｅ）Ａｂｓｔｒａｃｔ：Ｔｈｅｂｏｎｄａｇｅｎｕｍｂｅｒｂ（Ｇ）ｏｆａｇ...     

树的四类控制参数的束缚数

图的束缚数是图的控制数研究中的一个重要方面，它在某种程度上反映了图的控制数对边数的敏感度．本文通过对图的结构特征的分析．研究了树的四类控制参数的束缚数，即控制数，强控制数，弱控制数．分数控制数的束缚数．分别给出了其紧的上界．     

图的连通控制数与无赘数的一个不等式

设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(G)的关系,并证得上述猜想成立。     

Strong equality of domination parameters in trees

We study the concept of strong equality of domination parameters. Let P₁ and P₂ be properties of vertex subsets of a graph, and assume that every subset of V(G) with property P₂ also has property P₁. Let ψ₁(G) and ψ₂(G), respectively, denote the minimum cardinalities of sets with properties P₁ and P₂, respectively. Then ψ₁(G)ψ₂(G). If ψ₁(G)=ψ₂(G) and every ψ₁(G)-set is also a ψ₂(G)-set, then we say ψ₁(G) strongly equals ψ₂(G), written ψ₁(G)≡ψ₂(G). We provide a constructive characterization of the trees T such that γ(T)≡i(T), where γ(T) and i(T) are the domination and independent domination numbers, respectively. A constructive characterization of the trees T for which γ(T)=γ_t(T), where γ_t(T) denotes the total domination number of T, is also presented.     

3-γ-临界图G中关于i(G)=γ(G)的一个充分条件

如果图G满足γ（G）＝k且对图G中任两个相邻的点x,y有γ（G＋xy)=k-1,则称图G为k-γ-临界图,如果图G满足γ（G）＝k且对图G中任何距离为d的两点x,y有γ（G＋xy)=k-1,则称图G为k-(γ,d)－临界图。Sumner和Blitch猜想在3－γ－临界图中有γ（G）＝i(G).Oellermann和Swart猜想3－（γ,2）－临界图中有γ（G）＝i(G),这篇文章中我们提出3－γ－临界图中使γ（G）＝i(G)的一个充分条件。     

关于图的连通DOMINATION的若干结果

设G是n阶连通图.γ_c(G),d_c(G),i(G)和ir(G)分别表示G图的连通Domination数,连通Domatic数,独立Domination数和Irredundance数,k(G)表示G的连通度.本文证明了下列结论. (1) 如n≥3,则i(G) γ_c(G)≤n [n/3]-2; (2) γ_c(G)≤4ir(G)-2; (3) γ_c(G)≤k(G) 1; (4) 如G≠K_n,则d_c(G)≤k(G). 此外,本文给出了满足等式γ_c(G) γ_c(G)=n和γ_c(G) γ_c(G)=n 1的图G的一个特征.     

Total restrained bondage in graphs

A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V (G) S is also adjacent to a vertex in V (G) S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G E has no isolated vertex and the total restrained domination number of G E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph.     

Independent domination in triangle-free graphs

Let G be a simple graph of order n and minimum degree δ. The independent domination numberi(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish upper bounds, as functions of n and δ?n/2, for the independent domination number of triangle-free graphs, and over part of the range achieve best possible results.     

Independent domination in subcubic graphs of girth at least six

A set $S$ of vertices in a graph $G$ is an independent dominating set of $G$ if $S$ is an independent set and every vertex not in $S$ is adjacent to a vertex in $S$. The independent domination number, $i\left(G\right)$, of $G$ is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Löwenstein, and Rautenbach (2014) who proved that if $G$ is a bipartite, cubic graph of order $n$ and of girth at least $6$, then $i\left(G\right)\le \frac{4}{11}n$. We show that the bipartite condition can be relaxed, and prove that if $G$ is a cubic graph of order $n$ and of girth at least $6$, then $i\left(G\right)\le \frac{4}{11}n$.     

关于树T的γ/γc的界

控制γ和连通控制数γc是图的两个重要的控制参数，本文通过对树中的点进行恰当分类，给出了树中的γ/γc值的最好界，为刻画单圈图和双圈图中γ/γc值的界打下良好的基础。     

树的3-彩虹控制数的上界

对树的3-彩虹控制数进行研究,首先用构造法找到直径较小的树的3-彩虹控制数的上界.再通过分类讨论思想和数学归纳法得到一般的阶n大于等于5的树的3-彩虹控制数的上界.     

On the doubly connected domination number of a graph

For a given connected graph G = (V, E), a set is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.     

Locally Well-Dominated and Locally Independent Well-Dominated Graphs

 In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally well-dominated graphs. Received: September 13, 2001 Final version received: May 17, 2002 RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) RID="†" ID="†" Supported by RUTCOR RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) 05C75, 05C69 Acknowledgments. The authors thank the referees for valuable suggestions.     

A survey of selected recent results on total domination in graphs

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. In this paper, we offer a survey of selected recent results on total domination in graphs.     

Remarks on restrained domination and total restrained domination in graphs

The restrained domination number ^r(G) and the total restrained domination number _t ^r (G) of a graph G were introduced recently by various authors as certain variants of the domination number (G) of (G). A well-known numerical invariant of a graph is the domatic number d(G) which is in a certain way related (and may be called dual) to (G). The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.This research was supported by Grant MSM 245100303 of the Ministry of Education, Youth and Sports of the Czech Republic.     

Total outer-connected domination numbers of trees

Let G=(V,E) be a graph without an isolated vertex. A set DV(G) is a total dominating set if D is dominating, and the induced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total dominating set of G. A set DV(G) is a total outer-connected dominating set if D is total dominating, and the induced subgraph G[V(G)−D] is a connected graph. The total outer-connected domination number of G is the minimum cardinality of a total outer-connected dominating set of G. We characterize trees with equal total domination and total outer-connected domination numbers. We give a lower bound for the total outer-connected domination number of trees and we characterize the extremal trees.     

On the Roman domination number of a graph

A Roman dominating function of a graph G is a labeling f:V(G)?{0,1,2} such that every vertex with label 0 has a neighbor with label 2. The Roman domination number γ_R(G) of G is the minimum of ∑_v∈V(G)f(v) over such functions. A Roman dominating function of G of weight γ_R(G) is called a γ_R(G)-function. A Roman dominating function f:V?{0,1,2} can be represented by the ordered partition (V₀,V₁,V₂) of V, where V_i={v∈V∣f(v)=i}. Cockayne et al. [E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004) 11-22] posed the following question: What can we say about the minimum and maximum values of |V₀|,|V₁|,|V₂| for a γ_R-function f=(V₀,V₁,V₂) of a graph G? In this paper we first show that for any connected graph G of order n≥3, , where γ(G) is the domination number of G. Also we prove that for any γ_R-function f=(V₀,V₁,V₂) of a connected graph G of order n≥3, , and .