Back
 OJDM  Vol.10 No.1 , January 2020
The Number of Minimum Roman and Minimum Total Dominating Sets for Some Chessboard Graphs
Abstract: In this paper, both the roman domination number and the number of minimum roman dominating sets are found for any rectangular rook’s graph. In a similar fashion, the roman domination number and the number of minimum roman dominating sets are found on the square bishop’s graph for odd board sizes. Also found are the number of minimum total dominating sets associated with the light-colored squares when n ≡ 1(mod12)  (with n>1), and same for the dark-colored squares when n ≡ 7(mod12) .
Cite this paper: Burchett, P. (2020) The Number of Minimum Roman and Minimum Total Dominating Sets for Some Chessboard Graphs. Open Journal of Discrete Mathematics, 10, 31-44. doi: 10.4236/ojdm.2020.101004.
References

[1]   Watkins (2004) Across the Board: The Mathematics of Chessboard Problems. Princeton University Press, Princeton and Oxford.

[2]   Chaluvaraju, B. and Chaitra, V. (2012) Roman Domination in Complementary Prism Graphs. International Journal of Mathematical Combinatorics, 2, 24-31.

[3]   Cockayne, E.J., Dreyer Jr., P.A., Hedetniemi, S.M. and Hedetniemi, S.T. (2004) Roman Domination in Graphs. Discrete Mathematics, 178, 11-22.

[4]   Favaron, O., et al. (2009) On the Roman Domination Number of a Graph. Discrete Mathematics, 309, 3447-3451.

[5]   Fu, X.L., et al. (2009) Roman Domination in Regular Graphs. Discrete Mathematics, 309, 1528-1537.

[6]   Henning, M.A. and Hedetniemi, S.T. (1998) Defending the Roman Empire—A New Strategy. Discrete Mathematics, 266, 239-251.

[7]   Henning, M.A. (2003) Defending the Roman Empire from Multiple Attacks. Discrete Mathematics, 271, 101-115.

[8]   Pushpam, P.R.L. and Malini Mai, T.N.M. (2000) Roman Domination in Unicyclic Graphs. Journal of Discrete Mathematical Sciences and Crytography, 15, 201-213.

[9]   Muddebihal, M.H., Basavarajappa, D. and Sedamkar, A.R. (2010) Roman Domination in Line Graphs. Canadian Journal on Science and Engineering Mathematics, 1, 69-79.

[10]   Cockayne, E.J., Gamble, B. and Shepherd, B. (1986) Domination Parameters for the Bishop’s Graph. Discrete Mathematics, 58, 221-227.

[11]   Henning, M.A. and Yeo, A. (2013) Total Domination in Graphs. Springer-Verlag, New York.

[12]   Burchett, P.A. (2005) Paired and Total Domination on the Queen’s Graph. MS Thesis, East Tennessee State University, Johnson City.

[13]   Burchett, P.A. (2006) Paired, Total and Connected Domination on the Queen’s Graph. Congressus Numerantium, 178, 207-222.

 
 
Top