Research Article
BibTex RIS Cite
Year 2019, Volume: 11 Issue: 1, 40 - 47, 30.06.2019

Abstract

References

  • Alhashim, A., Desormeaux, W.J., Haynes, T.W., Roman domination in complementary prisms, Australasian journal of combinatorics, 68(2)(2017), 218--228.
  • Alvarez-Ruiz, M.P., Mediavilla-Gradolph, T., Sheikholeslami, S.M., Valenzuela-Tripodoro, J.C., Yero, I.G., On the strong Roman domination number of graphs, Discrete Applied Mathematics, 231(2017), 44--59.
  • Bermudo, S., Fernau, H., Sigarreta, J.M., The differential and the Roman domination number of a graph, Applicable Analysis and Discrete Mathematics, 8(2014), 155--171.
  • Beeler, R.A., Haynesa, T.W., Hedetniemi, S.T., Double Roman domination, Discrete Applied Mathematics, 211(2016), 23--29.
  • Cockayne, E.J., Dreyer, P.A., Hedetniemi, S.M., Hedetniemi, S.T., Roman domination in graphs, Discrete Mathematics, 278(2004), 11--22.
  • Chambers, E.W., Kinnersley, B., Prince, N. , West, D.B., Extermal problems for Roman domination, SIAM J. Discret Mathematics, 23(3)(2009), 1575--1586.
  • Desormeaux, W.J., Haynes, T.W., Henning, M.A., Domination parameters of a graph and it\'s complement, Discussiones Mathematicae Graph Theory, 38(2018), 203--215.
  • Gongora, J.A., Independent Domination in Complementary Prisms, Master\'s Thesis, East Tennessee State University, 2009.
  • Haynes, T.W., Hedetniemi, S.T., Slater, P.J., Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
  • Haynes, T.W., Holmes, K.R.S., Koessler, D.R., Sewell, L., Locating-Domination in Complementary Prisms of Paths and Cycles, Congressus Numerantium, 199(2009), 45--55.
  • Haynes, T.W., Henning, M.A., Slater, P.J., van der Merwe, L.C. , The complementary product of two graphs, Bulletin of the Institute of Combinatorics and its Applications, 51(2007), 21--30.
  • Haynes, T.W., Henning, M.A., van der Merwe, L.C., Domination and total domination in complemantary prisms, Journal of Combinatorial Optimization, 18(2009), 23--37.
  • Janseana, P., Ananchuen, N., Matching extension in complementary prism of regular graphs, Italian Journal of Pure and Applied Mathematics, 37(2017), 553--564.
  • Lewis, J.R., Differentials of Graphs, Master\'s Thesis, East Tennessee State University, 2004.
  • Mojdeh, D.A., Parsian, A., Masoumi, I., Characterization of double Roman trees, to appear in Ars Combinatoria, (2018).
  • West, D.B., Introduction to Graph theory, Second edition, Prentice Hall, USA, 2001.

Strong Roman Domination Number of Complementary Prism Graphs

Year 2019, Volume: 11 Issue: 1, 40 - 47, 30.06.2019

Abstract

Let $G=(V,E)$ be a simple graph  with vertex set $V=V(G)$, edge set $E=E(G)$ and from maximum degree $\Delta=\Delta(G)$. Also let
$f:V\rightarrow\{0,1,...,\lceil\frac{\Delta}{2}\rceil+1\}$ be a function that labels the vertices of $G$. Let $V_i=\{v\in V: f(v)=i\}$ for $i=0,1$ and let $V_2=V-(V_0\bigcup V_1)=\{w\in V: f(w)\geq2\}$. A function $f$ is called a strong Roman dominating function (StRDF) for $G$, if every $v\in V_0$ has a neighbor $w$, such that $w\in V_2$ and $f(w)\geq 1+\lceil\frac{1}{2}|N(w)\bigcap V_0|\rceil$. The minimum weight, $\omega(f)=f(V)=\Sigma_{v\in V} f(v)$, over all the strong Roman dominating functions of $G$, is called the strong Roman domination number of $G$ and we denote it by $\gamma_{StR}(G)$. An StRDF of minimum weight is called a $\gamma_{StR}(G)$-function. Let $\overline{G}$ be the complement of $G$. The complementary prism $G\overline{G}$ of $G$ is the graph formed from the disjoint union $G$ and $\overline{G}$ by adding the edges of a perfect matching between the corresponding vertices of $G$ and $\overline{G}$. In this paper, we investigate some properties of Roman, double Roman and strong Roman domination number of  $G\overline{G}$.

References

  • Alhashim, A., Desormeaux, W.J., Haynes, T.W., Roman domination in complementary prisms, Australasian journal of combinatorics, 68(2)(2017), 218--228.
  • Alvarez-Ruiz, M.P., Mediavilla-Gradolph, T., Sheikholeslami, S.M., Valenzuela-Tripodoro, J.C., Yero, I.G., On the strong Roman domination number of graphs, Discrete Applied Mathematics, 231(2017), 44--59.
  • Bermudo, S., Fernau, H., Sigarreta, J.M., The differential and the Roman domination number of a graph, Applicable Analysis and Discrete Mathematics, 8(2014), 155--171.
  • Beeler, R.A., Haynesa, T.W., Hedetniemi, S.T., Double Roman domination, Discrete Applied Mathematics, 211(2016), 23--29.
  • Cockayne, E.J., Dreyer, P.A., Hedetniemi, S.M., Hedetniemi, S.T., Roman domination in graphs, Discrete Mathematics, 278(2004), 11--22.
  • Chambers, E.W., Kinnersley, B., Prince, N. , West, D.B., Extermal problems for Roman domination, SIAM J. Discret Mathematics, 23(3)(2009), 1575--1586.
  • Desormeaux, W.J., Haynes, T.W., Henning, M.A., Domination parameters of a graph and it\'s complement, Discussiones Mathematicae Graph Theory, 38(2018), 203--215.
  • Gongora, J.A., Independent Domination in Complementary Prisms, Master\'s Thesis, East Tennessee State University, 2009.
  • Haynes, T.W., Hedetniemi, S.T., Slater, P.J., Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
  • Haynes, T.W., Holmes, K.R.S., Koessler, D.R., Sewell, L., Locating-Domination in Complementary Prisms of Paths and Cycles, Congressus Numerantium, 199(2009), 45--55.
  • Haynes, T.W., Henning, M.A., Slater, P.J., van der Merwe, L.C. , The complementary product of two graphs, Bulletin of the Institute of Combinatorics and its Applications, 51(2007), 21--30.
  • Haynes, T.W., Henning, M.A., van der Merwe, L.C., Domination and total domination in complemantary prisms, Journal of Combinatorial Optimization, 18(2009), 23--37.
  • Janseana, P., Ananchuen, N., Matching extension in complementary prism of regular graphs, Italian Journal of Pure and Applied Mathematics, 37(2017), 553--564.
  • Lewis, J.R., Differentials of Graphs, Master\'s Thesis, East Tennessee State University, 2004.
  • Mojdeh, D.A., Parsian, A., Masoumi, I., Characterization of double Roman trees, to appear in Ars Combinatoria, (2018).
  • West, D.B., Introduction to Graph theory, Second edition, Prentice Hall, USA, 2001.
There are 16 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Doost Ali Mojdeh

Ali Parsian This is me 0000-0001-6323-5956

İman Masoumi

Publication Date June 30, 2019
Published in Issue Year 2019 Volume: 11 Issue: 1

Cite

APA Mojdeh, D. A., Parsian, A., & Masoumi, İ. (2019). Strong Roman Domination Number of Complementary Prism Graphs. Turkish Journal of Mathematics and Computer Science, 11(1), 40-47.
AMA Mojdeh DA, Parsian A, Masoumi İ. Strong Roman Domination Number of Complementary Prism Graphs. TJMCS. June 2019;11(1):40-47.
Chicago Mojdeh, Doost Ali, Ali Parsian, and İman Masoumi. “Strong Roman Domination Number of Complementary Prism Graphs”. Turkish Journal of Mathematics and Computer Science 11, no. 1 (June 2019): 40-47.
EndNote Mojdeh DA, Parsian A, Masoumi İ (June 1, 2019) Strong Roman Domination Number of Complementary Prism Graphs. Turkish Journal of Mathematics and Computer Science 11 1 40–47.
IEEE D. A. Mojdeh, A. Parsian, and İ. Masoumi, “Strong Roman Domination Number of Complementary Prism Graphs”, TJMCS, vol. 11, no. 1, pp. 40–47, 2019.
ISNAD Mojdeh, Doost Ali et al. “Strong Roman Domination Number of Complementary Prism Graphs”. Turkish Journal of Mathematics and Computer Science 11/1 (June 2019), 40-47.
JAMA Mojdeh DA, Parsian A, Masoumi İ. Strong Roman Domination Number of Complementary Prism Graphs. TJMCS. 2019;11:40–47.
MLA Mojdeh, Doost Ali et al. “Strong Roman Domination Number of Complementary Prism Graphs”. Turkish Journal of Mathematics and Computer Science, vol. 11, no. 1, 2019, pp. 40-47.
Vancouver Mojdeh DA, Parsian A, Masoumi İ. Strong Roman Domination Number of Complementary Prism Graphs. TJMCS. 2019;11(1):40-7.