Disproof of a Conjecture on the Subdivision Domination Number of a Graph

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sd_γ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Haynes et al. (Discussiones Mathematicae Graph Theory 21 (2001) 239-253) conjectured that for any graph G with . In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of graphs.     

On the Characterization of Maximal Planar Graphs with a Given Signed Cycle Domination Number

Let G =(V, E) be a simple graph. A function f : E → {+1,-1} is called a signed cycle domination function(SCDF) of G if ∑_(e∈E(C))f(e) ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ'_(sc)(G) = min{∑_(e∈E)f(e)| f is an SCDF of G}. This paper will characterize all maximal planar graphs G with order n ≥ 6 and γ'_(sc)(G) = n.     

A New Bound on the Total Domination Subdivision Number

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that for every simple connected graph G of order n ≥ 3,

Domination versus total domination in claw-free cubic graphs

A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, every vertex in S is adjacent to some other vertex in S, then S is a total dominating set. The domination number $\gamma (G)$ of G is the minimum cardinality of a dominating set in G, while the total domination number ${\gamma }_t(G)$ of G is the minimum cardinality of total dominating set in G. A claw-free graph is a graph that does not contain $K_{1,3}$ as an induced subgraph. Let G be a connected, claw-free, cubic graph of order n. We show that if we exclude two graphs, then $\frac{{\gamma }_t(G)}{\gamma (G)}\le \frac{12}{7}$, and this bound is best possible. In order to prove this result, we prove that if we exclude four graphs, then ${\gamma }_t(G)\le \frac{3}{7}n$, and this bound is best possible. These bounds improve previously best known results due to Favaron and Henning (2008) [7], Southey and Henning (2010) [19].     

On the bounded domination number of tournaments

In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γ_k(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ_k(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices.     

Domination and upper domination of direct product graphs

Let $X_{\mathbb{Z}∕n\mathbb{Z}}$ denote the unitary Cayley graph of $\mathbb{Z}∕n\mathbb{Z}$. We present results on the tightness of the known inequality $\gamma \left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le {\gamma }_t\left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le g\left(n\right)$, where $\gamma$ and${\gamma }_t$ denote the domination number and total domination number, respectively, and $g$ is the arithmetic function known as Jacobsthal’s function. In particular, we construct integers $n$ with arbitrarily many distinct prime factors such that $\gamma \left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le {\gamma }_t\left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le g\left(n\right)?1$. We give lower bounds for the domination numbers of direct products of complete graphs and present a conjecture for the exact values of the upper domination numbers of direct products of balanced, complete multipartite graphs.     

Total domination dot-stable graphs

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Two vertices of G are said to be dotted (identified) if they are combined to form one vertex whose open neighborhood is the union of their neighborhoods minus themselves. We note that dotting any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most 2. A graph is total domination dot-stable if dotting any pair of adjacent vertices leaves the total domination number unchanged. We characterize the total domination dot-stable graphs and give a sharp upper bound on their total domination number. We also characterize the graphs attaining this bound.     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

图的双控制的一些新结果

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

具有最大控制数的连通图的刻画

设Ｇ为一个Ｐ阶图,γ（Ｇ）表示Ｇ的控制数．显然γ（Ｇ）≤［ｐ／２］．本文的目的是刻画达到这个上界的连通图．主要结果：（１）当ｐ为偶数时,γ（Ｇ）＝ｐ／２当且仅当Ｇ≈C₄或者Ｇ为某连通图的冠;（２）当ｐ为奇数时,γ（Ｇ）＝(p-1)/2当且仅当Ｇ的每棵生成树为定理３．１中所示的两类树之一．     

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)的一个充分条件。     

匹配数与控制数相等的图的结构性质

我们分别用γ(G)，β(G)和α(G)表示图G的控制数、匹配数和覆盖数，对任意连通图，有γ(G)≤β(G)≤α(G)成立，1998年，Randerath和Volkmann给出了控制数等于覆盖数的图的特征，本文首先证明了匹配数与控制数相等的图其最小度不超过2，而后给出了最小度为2的图的结构性质。     

粘合运算对图的控制参数的影响

简单图G的粘合运算G_(uv)指的是重合G的两个顶点{u,v}并且去掉重边和环所得到简单图的运算．本文考虑了粘合运算对图的4个控制参数γ(G),Γ(G),β(G),i(G)的影响．刻画了图G_(uv)与图G的控制参数γ(G),Γ(G),γ(G),i(G)之间的关系．及给出γ(G_(uv))=γ(G)-1和β(G_(uv)=β(G)-1的充要条件．     

On Domination Number of 4-Regular Graphs

Let G be a simple graph. A subset S V is a dominating set of G, if for any vertex v V – S there exists a vertex u S such that uv E(G). The domination number, denoted by (G), is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n, then (G) ⁴/₁₁ n     

极大全控点临界图

图G的点集S如果满足:VG-S(或VG)中每个点相邻于S中的某个点(或而不是它本身),则称点集S是一个控制集(或全控制集).图G的所有控制集(或全控制集)中最小基数的控制集(或全控制集)中的点数,称为控制数(或全控数),记为γ(G)(或γt(G)).在这篇文章中我们特征化γt-临界图且满足γt(G)=n-Δ(G)的图特征,这回答了Goddard等人提出的一个问题.     

Domination in Generalized Cayley Graph of Commutative Rings

Let $R$ be a commutative ring with identity and $n$ be a natural number. The generalized Cayley graph of $R$, denoted by $Γ^n_R$, is the graph whose vertex set is $R^n$\{0} and two distinct vertices $X$ and $Y$ are adjacent if and only if there exists an $n×n$ lower triangular matrix $A$ over $R$ whose entries on the main diagonal are non-zero such that $AX^T=Y^T$ or $AY^T=X^T$, where for a matrix $B$, $B^T$ is the matrix transpose of $B$. In this paper, we give some basic properties of$Γ^n_R$ and we determine the domination parameters of$Γ^n_R$.     

图的符号星控制数与因子

利用图的因子研究图的符号星控制数,简化了文献中已有的结果.     

关于图的减控制与符号控制

给定一个图G=(V,E),一个函数f:V→{-1,0,1}被称为G的减控制函数,如果对任意v∈V(G)均有∑_μ∈N[v]f(μ)≥1。G的减控制数定义为γ^-(G)=min{∑_v∈Vf(v)|f是G的减控制函数}。图G的符号控制函数的正如减控制函数,差别是广{-1,0,1}换成{-1,1}。符号控制数γ_s(G)是类似的。本文获得γ^-G)和γ_s(G)的一些下界。同时也证明并推广了 Jean Dunbar等提出的一个猜想,即对任意 n阶 2部图 G,均有γ^-(G)≥ 4(n+1^1/2-1)-n成立。     

Lower bounds for the domination number and the total domination number of direct product graphs

A sharp lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: . Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: γ(G×H)≥γ(G)+γ(H)−1. Infinite families of graphs that attain the bound are presented. For these graphs it also holds that γ_t(G×H)=γ(G)+γ(H)−1. Some additional parallels with the total domination number are made.