Realizations of the game domination number

Domination game is a game on a finite graph which includes two players. First player, Dominator, tries to dominate a graph in as few moves as possible; meanwhile the second player, Staller, tries to hold him back and delay the end of the game as long as she can. In each move at least one additional vertex has to be dominated. The number of all moves in the game in which Dominator makes the first move and both players play optimally is called the game domination number and is denoted by \(\gamma _g\) . The total number of moves in a Staller-start game is denoted by \(\gamma _g^{\prime }\) . It is known that \(|\gamma _g(G)-\gamma _g^{\prime }(G)|\le 1\) for any graph \(G\) . Graph \(G\) realizes a pair \((k,l)\) if \(\gamma _g(G)=k\) and \(\gamma _g^{\prime }(G)=l\) . It is shown that pairs \((2k,2k-1)\) for all \(k\ge 2\) can be realized by a family of 2-connected graphs. We also present 2-connected classes which realize pairs \((k,k)\) and \((k,k+1)\) . Exact game domination number for combs and 1-connected realization of the pair \((2k+1,2k)\) are also given.     

Roman game domination number of a graph

The Roman game domination number of an undirected graph G is defined by the following game. Players \(\mathcal {A}\) and \(\mathcal {D}\) orient the edges of the graph G alternately, with \(\mathcal {D}\) playing first, until all edges are oriented. Player \(\mathcal {D}\) (frequently called Dominator) tries to minimize the Roman domination number of the resulting digraph, while player \(\mathcal {A}\) (Avoider) tries to maximize it. This game gives a unique number depending only on G, if we suppose that both \(\mathcal {A}\) and \(\mathcal {D}\) play according to their optimal strategies. This number is called the Roman game domination number of G and is denoted by \(\gamma _{Rg}(G)\). In this paper we initiate the study of the Roman game domination number of a graph and we establish some bounds on \(\gamma _{Rg}(G)\). We also determine the Roman game domination number for some classes of graphs.     

Signed mixed Roman domination numbers in graphs

Let \(G = (V;E)\) be a simple graph with vertex set \(V\) and edge set \(E\). A signed mixed Roman dominating function (SMRDF) of \(G\) is a function \(f: V\cup E\rightarrow \{-1,1,2\}\) satisfying the conditions that (i) \(\sum _{y\in N_m[x]}f(y)\ge 1\) for each \(x\in V\cup E\), where \(N_m[x]\) is the set, called mixed closed neighborhood of \(x\), consists of \(x\) and the elements of \(V\cup E\) adjacent or incident to \(x\) (ii) every element \(x\in V\cup E\) for which \(f(x) = -1\) is adjacent or incident to at least one element \(y\in V\cup E\) for which \(f(y) = 2\). The weight of a SMRDF \(f\) is \(\omega (f)=\sum _{x\in V\cup E}f(x)\). The signed mixed Roman domination number \(\gamma _{sR}^*(G)\) of \(G\) is the minimum weight of a SMRDF of \(G\). In this paper we initiate the study of the signed mixed Roman domination number and we present bounds for this parameter. In particular, we determine this parameter for some classes of graphs.     

Total and paired domination numbers of toroidal meshes

Let G be a graph without isolated vertices. The total domination number of G is the minimum number of vertices that can dominate all vertices in G, and the paired domination number of G is the minimum number of vertices in a dominating set whose induced subgraph contains a perfect matching. This paper determines the total domination number and the paired domination number of the toroidal meshes, i.e., the Cartesian product of two cycles C _n and C _m for any n≥3 and m∈{3,4}, and gives some upper bounds for n,m≥5.     

Total and paired domination numbers of $$C_m$$ bundles over a cycle $$C_n$$Cn

Let \(G=(V,E)\) be a simple graph without isolated vertices. A set \(S\) of vertices is a total dominating set of a graph \(G\) if every vertex of \(G\) is adjacent to some vertex in \(S\). A paired dominating set of \(G\) is a dominating set whose induced subgraph has a perfect matching. The minimum cardinality of a total dominating set (respectively, a paired dominating set) is the total domination number (respectively, the paired domination number). Hu and Xu (J Combin Optim 27(2):369–378, 2014) computed the exact values of total and paired domination numbers of Cartesian product \(C_n\square C_m\) for \(m=3,4\). Graph bundles generalize the notions of covering graphs and Cartesian products. In this paper, we generalize these results given in Hu and Xu (J Combin Optim 27(2):369–378, 2014) to graph bundle and compute the total domination number and the paired domination number of \(C_m\) bundles over a cycle \(C_n\) for \(m=3,4\). Moreover, we give the exact value for the total domination number of Cartesian product \(C_n\square C_5\) and some upper bounds of \(C_m\) bundles over a cycle \(C_n\) where \(m\ge 5\).     

Power domination with bounded time constraints

Based on the power observation rules, the problem of monitoring a power utility network can be transformed into the graph-theoretic power domination problem, which is an extension of the well-known domination problem. A set \(S\) is a power dominating set (PDS) of a graph \(G=(V,E)\) if every vertex \(v\) in \(V\) can be observed under the following two observation rules: (1) \(v\) is dominated by \(S\), i.e., \(v \in S\) or \(v\) has a neighbor in \(S\); and (2) one of \(v\)’s neighbors, say \(u\), and all of \(u\)’s neighbors, except \(v\), can be observed. The power domination problem involves finding a PDS with the minimum cardinality in a graph. Similar to message passing protocols, a PDS can be considered as a dominating set with propagation that applies the second rule iteratively. This study investigates a generalized power domination problem, which limits the number of propagation iterations to a given positive integer; that is, the second rule is applied synchronously with a bounded time constraint. To solve the problem in block graphs, we propose a linear time algorithm that uses a labeling approach. In addition, based on the concept of time constraints, we provide the first nontrivial lower bound for the power domination problem.     

Distance domination in graphs with given minimum and maximum degree

For an integer \(k \ge 1\), a distance k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V(G) is at distance at most k from some vertex of S. The distance k-domination number \(\gamma _k(G)\) of G is the minimum cardinality of a distance k-dominating set of G. In this paper, we establish an upper bound on the distance k-domination number of a graph in terms of its order, minimum degree and maximum degree. We prove that for \(k \ge 2\), if G is a connected graph with minimum degree \(\delta \ge 2\) and maximum degree \(\Delta \) and of order \(n \ge \Delta + k - 1\), then \(\gamma _k(G) \le \frac{n + \delta - \Delta }{\delta + k - 1}\). This result improves existing known results.     

Bounds on the domination number of a digraph

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. The domination number of D, denoted by \(\gamma (D)\), is the minimum cardinality of a dominating set of D. The Slater number \(s\ell (D)\) is the smallest integer t such that t added to the sum of the first t terms of the non-increasing out-degree sequence of D is at least as large as the order of D. For any digraph D of order n with maximum out-degree \(\Delta ^+\), it is known that \(\gamma (D)\ge \lceil n/(\Delta ^++1)\rceil \). We show that \(\gamma (D)\ge s\ell (D)\ge \lceil n/(\Delta ^++1)\rceil \) and the difference between \(s\ell (D)\) and \(\lceil n/(\Delta ^++1)\rceil \) can be arbitrarily large. In particular, for an oriented tree T of order n with \(n_0\) vertices of out-degree 0, we show that \((n-n_0+1)/2\le s\ell (T)\le \gamma (T)\le 2s\ell (T)-1\) and moreover, each value between the lower bound \(s\ell (T)\) and the upper bound \(2s\ell (T)-1\) is attainable by \(\gamma (T)\) for some oriented trees. Further, we characterize the oriented trees T for which \(s\ell (T)=(n-n_0+1)/2\) hold and show that the difference between \(s\ell (T)\) and \((n-n_0+1)/2\) can be arbitrarily large. Some other elementary properties involving the Slater number are also presented.     

k-tuple total domination in cross products of graphs

For k??1 an integer, a set S of vertices in a graph G with minimum degree at least?k is a k-tuple total dominating set of G if every vertex of G is adjacent to at least k vertices in S. The minimum cardinality of a k-tuple total dominating set of G is the k-tuple total domination number of G. When k=1, the k-tuple total domination number is the well-studied total domination number. In this paper, we establish upper and lower bounds on the k-tuple total domination number of the cross product graph G×H for any two graphs G and H with minimum degree at least?k. In particular, we determine the exact value of the k-tuple total domination number of the cross product of two complete graphs.     

Graphs with small balanced decomposition numbers

A balanced coloring of a graph \(G\) is an ordered pair \((R,B)\) of disjoint subsets \(R,B \subseteq V(G)\) with \(|R|=|B|\) . The balanced decomposition number  \(f(G)\) of a connected graph \(G\) is the minimum integer \(f\) such that for any balanced coloring \((R,B)\) of \(G\) there is a partition \(\mathcal{P}\) of \(V(G)\) such that \(S\) induces a connected subgraph with \(|S| \le f\) and \(|S \cap R| = |S \cap B|\) for \(S \in \mathcal{P}\) . This paper gives a short proof for the result by Fujita and Liu (2010) that a graph \(G\) of \(n\) vertices has \(f(G)=3\) if and only if \(G\) is \(\lfloor \frac{n}{2} \rfloor \) -connected but is not a complete graph.     

Aspects of quality . . . and world domination!

Training, learning and development tend to be regarded as central to the success of every organization and the nation. However, not all organizations are able or willing to invest resources in such processes. The paper presents a view that training, learning and development occur as a consequence of successful persuasive actions in a chain of talk, which draw on the discursive and rhetorical resources of an emerging learning movement. Utilizing the findings from an examination of data from the UK Department of Education and Skills-sponsored National Training Award winners, the paper provides an employment of actor-network theory and the sociology of translation to show how some organizations make the case for training, learning and development as a virtuous endeavour. It concludes by suggesting that what is needed is a more detailed understanding of how the case for the adoption of training, learning and development, or not, within organizations is made meaningful.     

Competing with Japan—The rules of the game

This paper explains that, to deal with the Japanese challenge, it is important to understand the comprehensive nature of that challenge. The challenge covers every function and every phase of the product development and marketing cycle. Therefore, solutions must not be piecemeal. In writing this paper, the author draws extensively on his working and consulting experience.     

创业团队共享领导对企业创新绩效的影响机制

在第三方再制造商参与废旧产品的回收再制造活动时,往往会涉及专利许可与政府规制问题.构建了制造商与再制造商之间的动态博弈模型,分别探讨了无专利许可无政府规制、有专利许可无政府规制、有专利许可有政府规制3种模式下企业的生产决策和再制造绩效水平.研究发现,以制造商主导的专利许可机制对再制造活动具有一定的抑制作用,仅当再制造产业发展较为成熟时才能为制造商带来显著收益;以政府主导的生产者责任延伸制度有利于促进再制造产业发展,尤其在再制造业发展初期可有效提升产品回收再制造率,并且该制度对再制造的促进作用与再制造带来的环境效益呈正相关.研究结论对专利产品再制造过程中各企业的生产策略选择以及政府在再制造产业发展各阶段中财政政策的制定具有一定的参考价值.     

资产收益序列相依下的多阶段投资博弈模型

现有投资组合优化研究普遍假设投资者之间相互独立,且假定标的资产在不同阶段的收益序列不具相关性.然而在实际投资过程中,投资者往往是相互影响,资产收益序列也存在相依特征.基于多阶段投资组合优化和纳什均衡理论,利用相对绩效来刻画投资者之间的博弈现象,以每个投资者的相对终端财富的期望效用水平为目标,构建多阶段投资组合博弈模型.在资产收益序列相依情形下,给出了纳什均衡投资策略和相应值函数的解析表达式,以及纳什均衡投资策略与传统策略的关系.采用累计经验分布函数和夏普比率等指标,对纳什均衡投资策略与传统策略进行仿真比较,分析了纳什均衡投资策略随投资者反应敏感系数的变化趋势.结果表明:相比于传统的投资策略,当考虑竞争对手的相对绩效时,纳什均衡策略投资者更愿意冒高风险去追求高收益;并且投资者的反应敏感系数越大,其对风险的偏好程度也越高.     

The domination number of Cartesian product of two directed paths

Let γ(P _m □P _n ) be the domination number of the Cartesian product of directed paths P _m and P _n for m,n≥2. Liu et al. in (J. Comb. Optim. 22(4):651–662, 2011) determined the value of γ(P _m □P _n ) for arbitrary n and m≤6. In this work we give the exact value of γ(P _m □P _n ) for any m,n and exhibit dominating sets of minimum cardinality.     

On the upper total domination number of Cartesian products of graphs

In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63–69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ _t (G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, Γ _t (G)Γ _t (H)≤2Γ _t (G □ H). Research of M.A. Henning supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.