Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Number of Dominating Sets in Cylindric Square Grid Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

A dominating set of a graph is a subset D of the vertices such that every vertex not in D is adjacent to some vertex of D. In this paper, we introduce several variants of dominating sets in the square grid, periodic square grid and cylindric square grid by considering translation symmetry. We provide their exact enumerations in terms of domination polynomials. We also analyze the asymptotic behavior of the growth rates of their cardinality.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Alanko, S., Crevals, S., Isopoussu, A., Östergard, P., Pettersson, V.: Computing the domination number of grid graphs. Electron. J. Combin. 18, #P141 (2011)

    Article  MathSciNet  Google Scholar 

  2. Alikhani, S., Peng, Y.: Introduction to domination polynomial of a graph. ARS Combin. 114, 257–266 (2014)

    MathSciNet  MATH  Google Scholar 

  3. Chang, T., Clark, W.: The domination numbers of the \(5 \times n\) and the \(6 \times n\) grid graphs. J. Graph Theory 17, 81–107 (1993)

    Article  MathSciNet  Google Scholar 

  4. Chang, T., Clark, W., Hare, E.: Domination numbers of complete grid graphs. I. ARS Combin. 38, 97–111 (1994)

    MathSciNet  MATH  Google Scholar 

  5. Chérifi, R., Gravier, S., Zighem, I.: Bounds on domination number of complete grid graphs. ARS Combin. 60, 307–311 (2001)

    MathSciNet  MATH  Google Scholar 

  6. Cockayne, E., Hare, E., Hedetniemi, S., Wimer, T.: Bounds for the domination number of grid graphs. Congr. Numer. 47, 217–228 (1985)

    MathSciNet  Google Scholar 

  7. Goncalves, D., Pinlou, A., Rao, M., Thomassé, S.: The domination number of grids. SIAM J. Discrete Math. 25, 1443–1453 (2011)

    Article  MathSciNet  Google Scholar 

  8. Guichard, D.: A lower bound for the domination number of complete grid graphs. J. Combin. Math. Combin. Comput. 49, 215–220 (2004)

    MathSciNet  MATH  Google Scholar 

  9. Haynes, T., Hedetniemi, S., Slater, P.: Fundamentals of domination in graphs. Marcel Dekker, New York (1998)

    MATH  Google Scholar 

  10. Hedetniemi, S., Laskar, R.: Topics on domination. North Holland, New York (1991)

    MATH  Google Scholar 

  11. Jacobson, M., Kinch, L.: On the domination number of products of a graph I. ARS Combin. 18, 33–44 (1983)

    MathSciNet  MATH  Google Scholar 

  12. Klavžar, S., Seifter, N.: Dominating Cartesian products of cycles. Discrete Appl. Math. 59, 129–136 (1995)

    Article  MathSciNet  Google Scholar 

  13. Kotek, T., Preen, J., Simon, F., Tittmann, P., Trinks, M.: Recurrence relations and splitting formulas for the domination polynomial. Electron. J. Combin. 19, #P47 (2012)

    Article  MathSciNet  Google Scholar 

  14. Livingston, M., Stout, Q.: Constant time computation of minimum dominating sets. Congr. Numer. 105, 116–128 (1994)

    MathSciNet  MATH  Google Scholar 

  15. Oh, S.: Maximal independent sets on a grid graph. Discrete Math. 340, 2762–2768 (2017)

    Article  MathSciNet  Google Scholar 

  16. Oh, S.: State matrix recursion method and monomer-dimer problem. Discrete Math. 342, 1434–1445 (2019)

    Article  MathSciNet  Google Scholar 

  17. Oh, S., Lee, S.: Enumerating independent vertex sets in grid graphs. Linear Algebra Appl. 510, 192–204 (2016)

    Article  MathSciNet  Google Scholar 

  18. Oh, S., Hong, K., Lee, H., Lee, H.J.: Quantum knots and the number of knot mosaics. Quantum Inf. Process. 14, 801–811 (2015)

    Article  MathSciNet  Google Scholar 

  19. Sloane, N.: The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org/ (1996)

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Korea University, Seoul, 02841, Korea

    Seungsang Oh

Authors
  1. Seungsang Oh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Seungsang Oh.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work was supported by Institute for Information and communications Technology Planning and Evaluation (IITP) grant funded by the Korea government(MSIT) (No. 2019-0-00033, Study on Quantum Security Evaluation of Cryptography based on Computational Quantum Complexity).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Oh, S. Number of Dominating Sets in Cylindric Square Grid Graphs. Graphs and Combinatorics 37, 1357–1372 (2021). https://doi.org/10.1007/s00373-021-02323-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-021-02323-8

Keywords

Mathematics Subject Classification

Search

Navigation