# 两类冠图的符号罗马控制数The Signed Roman Domination Number of Two Classes Corona Graph

• 全文下载: PDF(449KB)    PP.91-95   DOI: 10.12677/PM.2020.102014
• 下载量: 85  浏览量: 170   国家自然科学基金支持

Let G=(V,E) be a simple undirected graph and denote f(S)=∑v∈sf(v) for S⊆V. A real-valued function f:V→{-1,1,2} is called a signed Roman domination function if f satisfies the conditions that 1) f(N[v])≥1 for any v∈V, and 2) every vertex v for which f(v)=-1 is adjacent to a vertex u for which is f(u)=2. The signed Roman domination number of G is γsR(G)=min{f(V)|f is a signed Roman domination function f of G} . In this paper, we determine exact values of the signed Roman domination number of two classes graph, such as a Corona of k-regular graph and wheel graph by constructive method and exhaustive method.

1. 引言

$G=\left(V,E\right)$ 是一个图，其顶点集 $V=V\left(G\right)$ 和边集 $E=E\left(G\right)$。对任意 $u\in V\left(G\right)$，则 ${N}_{G}\left(u\right)$ 为u点在G中的邻域， ${N}_{G}\left[u\right]={N}_{G}\left(u\right)\cup \left\{u\right\}$ 为u点在G中的闭邻域， ${d}_{G}\left(u\right)=|{N}_{G}\left(u\right)|$ 为u点在G中的度，而 $\delta =\delta \left(G\right)$$\Delta =\Delta \left(G\right)$ 分别为图G的最小度和最大度。在不致混淆情况下，可将 ${N}_{G}\left(u\right)$${N}_{G}\left[u\right]$$\Delta \left(G\right)$$\delta \left(G\right)$ 分别简单记为 $N\left(u\right)$$N\left[u\right]$$\Delta$$\delta$。用 ${C}_{n}$${P}_{n}$${K}_{n}$ 分别表示n阶圈、路和完全图。k-正则图G是指G

2. 基本概念

$f:V↦\left\{-1,1,2\right\}$ 满足以下两个条件：

1) 对于任意的顶点 $v\in V$，均有 $f\left(N\left[v\right]\right)\ge 1$ 成立；

2) 如果对任意的顶点 $v\in V$，若 $f\left(v\right)=-1$

${\gamma }_{sR}\left(G\right)={\sum }_{v\in V}f\left(v\right)$,

3. 主要定理及其证明

${\gamma }_{sR}\left(G\right)=n\left(1-2k\right)$.

$V\left({G}^{\prime }\right)=\left\{{v}_{1},{v}_{2},\cdots ,{v}_{n}\right\}$, ,

$f=\left({V}_{2},{V}_{1},{V}_{-1}\right)$ 是图G的 ${\gamma }_{sR}\left(G\right)$ -函数，由符号罗马控制数定义知

$f\left[{v}_{1}\right]+\cdots +f\left[{v}_{n}\right]\ge n$,

$\begin{array}{l}\underset{j=1}{\overset{2k+1}{\sum }}f\left({v}_{1}^{j}\right)+\cdots +\underset{j=1}{\overset{2k+1}{\sum }}f\left({v}_{n}^{j}\right)+\left(k+1\right)\underset{i=1}{\overset{n}{\sum }}f\left({v}_{i}\right)\\ =f\left(V\left(G\right)\right)+k\underset{i=1}{\overset{n}{\sum }}f\left({v}_{i}\right)\ge n\end{array}$

$\begin{array}{c}{\gamma }_{sR}\left(G\right)=f\left(V\left(G\right)\right)\\ \ge n-k\left(f\left({v}_{1}\right)+\cdots +f\left({v}_{n}\right)\right)\\ \ge n-k\cdot 2n=n\left(1-2k\right)\end{array}$.

$g\left(v\right)=\left\{\begin{array}{l}+2,当v={v}_{i},i=1,\cdots ,n\\ -1,否则\end{array}$

$g\left[v\right]=2\left(k+1\right)-\left(2k+1\right)=1$.

${\gamma }_{sR}\left(G\right)\le g\left(V\right)=2|{V}_{2}|+|{V}_{1}|-|{V}_{-1}|=n\left(1-2k\right)$.

${\gamma }_{sR}\left(G\right)=n\left(1-2k\right)$.

${\gamma }_{sR}\left(G\right)=1-7n$.

$V\left({W}_{n\text{+}1}\right)=\left\{{v}_{0},{v}_{1},\cdots ,{v}_{n}\right\}$

$V\left(G\right)=\left\{{v}_{i}^{j}|i=1,2,\cdots n,j=1,2,\cdots ,7\right\}\cup \left\{{v}_{i}^{k}|i=0,k=1,2,\cdots ,2n+1\right\}\cup V\left({W}_{n+1}\right)$,

$f=\left({V}_{2},{V}_{1},{V}_{-1}\right)$ 是图G的 ${\gamma }_{sR}\left(G\right)$ -函数，由符号罗马控制数定义知

$f\left[{v}_{1}\right]+\cdots +f\left[{v}_{n}\right]+f\left[{v}_{n+1}\right]\ge n+1$,

$\underset{j=1}{\overset{7}{\sum }}f\left({v}_{1}^{j}\right)+\underset{j=1}{\overset{7}{\sum }}f\left({v}_{2}^{j}\right)+\cdots +\underset{j=1}{\overset{7}{\sum }}f\left({v}_{n}^{j}\right)+\underset{j=1}{\overset{2n+1}{\sum }}f\left({v}_{0}^{j}\right)+4\underset{i=1}{\overset{n}{\sum }}f\left({v}_{i}\right)+\left(n+1\right)f\left({v}_{0}\right)\ge n+1$,

$f\left(V\left(G\right)\right)+3\underset{i=1}{\overset{n}{\sum }}f\left({v}_{i}\right)+nf\left({v}_{0}\right)\ge n+1$.

$\begin{array}{c}{\gamma }_{sR}\left(G\right)=f\left(V\left(G\right)\right)\\ \ge n+1-3\left(f\left({v}_{1}\right)+\cdots +f\left({v}_{n}\right)\right)-n\cdot f\left({v}_{0}\right)\\ \ge n+1-6n-2n=1-7n\end{array}$.

$g\left(v\right)=\left\{\begin{array}{l}+2,当v={v}_{i},i=0,1,2,\cdots ,n\\ -1,否则\end{array}$,

$\begin{array}{c}{\gamma }_{sR}\left(G\right)\le g\left(V\right)=2|{V}_{2}|+|{V}_{1}|-|{V}_{-1}|\\ =2\left(n+1\right)-7n-\left(2n+1\right)=1-7n\end{array}$.

${\gamma }_{sR}\left(G\right)=1-7n$.

 [1] Bondy, J.A. and Murty, U.S.R. (1977) Graph Theory with Applications. Macmillan, London. [2] Dunbar, J.E., Hedetniemi, S.T., Henning, M.A. and Slater, P.J. (1995) Signed Domination in Graphs. Graph Theory, Combinatorics and Application, 1, 311-322. [3] 徐保根. 图的控制理论[M]. 北京: 科学出版社, 2008. [4] Henning, M.A. (2004) Signed Total Domination in Graphs. Discrete Mathematics, 278, 109-125.https://doi.org/10.1016/j.disc.2003.06.002 [5] Xu, B.G. (2009) On Signed Cycle Domination Numbers in Graphs. Discrete Mathematics, 309, 1007-1012.https://doi.org/10.1016/j.disc.2008.01.007 [6] Volkmann, L. (2016) On the Signed Total Roman Domination and Domatic Numbers of Graphs. Discrete Applied Mathematics, 214, 179-186. https://doi.org/10.1016/j.dam.2016.06.006 [7] Ahangar, H.A., Amjadi, J., Sheikholeslami, S.M. and Zhao, Y. (2016) Signed Roman Edge Domination Numbers in Graphs. Journal of Combinatorial Optimization, 31, 333-346. https://doi.org/10.1007/s10878-014-9747-8 [8] Asgharsharghi, L. and Sheikholeslami, S.M. (2017) Signed Total Roman Edge Domination in Graphs. Discussions Mathematicae Graph Theory, 37, 1039-1053.https://doi.org/10.7151/dmgt.1984 [9] Abdollahzadeh Ahangar, H., Henning, M.A., Löwenstein, C., Zhao, Y. and Samodivkin, V. (2014) Signed Roman Domination in Graphs. Journal of Combinatorial Optimization, 27, 241-255.https://doi.org/10.1007/s10878-012-9500-0 [10] Zhao, Y.C. and Miao, L.Y. (2017) Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels. Communications in Mathematical Research, 33, 318-326. [11] 尹凯, 陈学刚. 完全多部图的符号罗马控制数[J]. 汕头大学学报, 2017, 31(4): 25-34.