Back
 OJDM  Vol.6 No.3 , July 2016
The Independence-Separation Problem on the 3-D Rook’s Graph
Paul A. Burchett
Show more
Abstract: Both independence and independence-separation problems on chessboard graphs have been studied in detail, with hundreds of papers in the broader independence category, and several on the independence-separation problem variant for chessboard graphs. In this paper, the inde-pendence-separation problem is considered on the d-dimensional rook’s graph. A lower bound of k, for , is found for the independence-separation number on the d-dimensional rook’s graph, denoted by . For the case where , it is found that when n is odd and , . Conjecture and discussion are added.
Keywords: Chess, Independence-Separation Number, Independence Number, p-Dimensional Grid-Line Graphs, p-Dimensional Rook’s Graph
Cite this paper: Burchett, P. (2016) The Independence-Separation Problem on the 3-D Rook’s Graph. Open Journal of Discrete Mathematics, 6, 167-173. doi: 10.4236/ojdm.2016.63014.
References

[1]   Chatham, R.D. (2009) Reflections on the N + k Queens Problem. College Mathematics Journal, 40, 204-210.
http://dx.doi.org/10.4169/193113409X469433

[2]   Chatham, R.D., Fricke, G.H. and Skaggs, R.D. (2006) The Queens Separation Problem. Utilitas Mathematica, 69, 129-141.

[3]   Chatham, R.D., Doyle, M., Fricke, G.H., Reitmann, J., Skaggs, R.D. and Wolff, M. (2009) Independence and Domination Separation in Chessboard Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 68, 3-17.

[4]   Chatham, R.D., Doyle, M., Miller, J.J., Rogers, A.M., Skaggs, R.D. and Ward, J.A. (2009) Algorithm Performance for Chessboard Separation Problems. Journal of Combinatorial Mathematics and Combinatorial Computing, 70, 127-142.

[5]   Zhao, K. (1998) The Combinatorics of Chessboards. PhD Thesis, CUNY, York.

[6]   Brualdi, R.A., Kiernan, K.P., Meyer, S.A. and Schroeder, M.W. (2013) Patterns of Alternating Sign Matrices. Linear Algebra and Its Applications, 438, 3967-3990.
http://dx.doi.org/10.1016/j.laa.2012.03.009

 
 
Top