Skip to main content
SpringerLink
Log in

Bondage Numbers of Mycielski Graphs

  • Published:
Bulletin of the Malaysian Mathematical Sciences Society Aims and scope Submit manuscript

Abstract

The bondage number \(b(G)\) of a nonempty graph \(G\) is the smallest number of edges, removal of which from \(G\) results in a graph with domination number greater than that of \(G\). In this paper, we study the bondage number of Mycielski graphs. First, we present some properties of dominating sets and give sharp upper bounds for bondage numbers of Mycielski graphs. Second, we obtain a characterization of Mycielski graphs of trees bondage numbers of which are 1. Finally, we calculate the exact values for bondage numbers of Mycielski graphs underlying graphs of which are complete graphs, paths, cycles, complete \(t\)-partite graphs, etc.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Carlson, K., Develin, M.: On the bondage number of planar and directed graphs. Discret. Math. 306(8–9), 820–826 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  2. Chen, X.-G., Xing, H.-M.: Domination parameters in Mycielski graphs. Util. Math. 71, 235–244 (2006)

    MathSciNet  MATH  Google Scholar 

  3. Dettlaff, M., Lemańska, M., Yero, I.G.: Bondage number of grid graphs. Discret. Appl. Math. 167, 94–99 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  4. Dunbar, J.E., Haynes, T.W., Teschner, U., Volkmann, L.: Bondage, insensitivity, and reinforcement. In: Haynes, T.W., Hedetniemi, S.T., Slater, T. (eds.) Domination in Graphs: Advanced Topics. Monogr. Textbooks Pure Appl. Math., vol. 209, pp. 471–489. Marcel Dekker, New York (1998)

    Google Scholar 

  5. Fink, J.F., Jacobson, M.S., Kinch, L.F., Roberts, J.: The bondage number of a graph. Discret. Math. 86, 47–57 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  6. Fisher, D.C., McKenna, P.A., Boyer, E.D.: Hamiltonicity, diameter, domination, packing and biclique partitions of Myscielski’s graphs. Discret. Appl. Math. 84, 93–105 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  7. Fisher, D.C.: Fractional dominations and total dominations of graph complements. Discret. Appl. Math. 122, 283–291 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  8. Frucht, R., Harary, F.: On the corona of two graphs. Aequationes Math. 4, 322–325 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  9. Hartnell, B.L., Rall, D.F.: A characterization of trees in which no edge is essential to the domination number. Ars Combin. 33, 65–76 (1992)

    MathSciNet  MATH  Google Scholar 

  10. Hartnell, B.L., Jørgensen, L.K., Vestergaard, P.D., Whitehead, C.: Edge stability of the \(k\)-domination number of trees. Bull. Inst. Combin. Appl. 22, 31–40 (1998)

    MathSciNet  MATH  Google Scholar 

  11. Hartnell, B.L., Rall, D.F.: Bounds on the bondage number of a graph. Discret. Math. 128, 173–177 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  12. Henning, M.A.: Trees with large total domination number. Util. Math. 60, 99–106 (2001)

    MathSciNet  MATH  Google Scholar 

  13. Hu, F.-T., Lu, Y., Xu, J.-M.: The total bondage number of grid graphs. Discret. Appl. Math. 160, 2408–2418 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hu, F.-T., Xu, J.-M.: On the complexity of the bondage and reinforcement problems. J. Complex. 28(2), 192–201 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. Hu, F.-T., Sohn, M.Y.: The algorithmic complexity of bondage and reinforcement problems in bipartite graphs. Theor. Comput. Sci. 535, 46–53 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  16. Huang, J., Xu, J.-M.: The bondage numbers and efficient dominations of vertex-transitive graphs. Discret. Math. 308(4), 571–582 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  17. Kang, L.-Y., Sohn, M.Y., Kim, H.K.: Bondage number of the discrete torus \(C_n\times C_4\). Discret. Math. 303, 80–86 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  18. Kang, L., Yuan, J.: Bondage number of planar graphs. Discret. Math. 222, 191–198 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  19. Kavaskar, T.: Further Results on the Mycielskian of Graphs. Combinatorial Algorithms. Springer, Berlin (2012)

    MATH  Google Scholar 

  20. Lin, W., Wu, J., Che Bor. Lam, P., Gu, G.: Several parameters of generalized Mycielskians. Discret. Appl. Math. 154, 1173–1182 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  21. Mojdeh, D.A., Jafari Rad, N.: On domination and its forcing in Mycielski’s graphs. Sci. Iran. 15(2), 218–222 (2008)

    MathSciNet  MATH  Google Scholar 

  22. Mycielski, J.: Sur le coloriage des graphes. Colloq. Math. 3, 161–162 (1955)

    MathSciNet  MATH  Google Scholar 

  23. Teschner, U.: A new upper bound for the bondage number of graphs with small domination number. Australas. J. Combin. 12, 27–35 (1995)

    MathSciNet  MATH  Google Scholar 

  24. Teschner, U.: New results about the bondage number of a graph. Discret. Math. 171, 249–259 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  25. Topp, J., Vestergaard, P.D.: \(\alpha _k\) and \(\gamma _k\)-stable graphs. Discret. Math. 212, 149–160 (2000)

    Article  MathSciNet  Google Scholar 

  26. Varghese, S., Vijayakumar, A.: Power domination in some classes of graphs. EuroComb’11, (2011)

  27. Xu, J.-M.: Theory and Application of Graphs. Kluwer Academic Publishers, Dordrecht (2003)

    Book  MATH  Google Scholar 

  28. Xu, J.-M.: On bondage numbers of graphs: a survey with some comments. Inter. Journ. Comb. 2013, Article ID: 595210, p. 34 (2013)

Download references

Acknowledgments

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science, and Technology (2012R1A1A2005115). The first author was supported by NNSF of China (No. 11401004).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Anhui University, Hefei, 230601, China

    Fu-Tao Hu

  2. Department of Mathematics, Changwon National University, Changwon, 641-773, Korea

    Moo Young Sohn

  3. Department of Mathematics, Yeungnam University, Gyeongsan, 712-749, Korea

    Jaeun Lee

Authors
  1. Fu-Tao Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Moo Young Sohn
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jaeun Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Moo Young Sohn.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hu, FT., Sohn, M.Y. & Lee, J. Bondage Numbers of Mycielski Graphs. Bull. Malays. Math. Sci. Soc. 39 (Suppl 1), 229–245 (2016). https://doi.org/10.1007/s40840-015-0116-2

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40840-015-0116-2

Keywords

Mathematics Subject Classification

Search

Navigation