[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Partitioning a Graph into Global Powerful k-Alliances

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

Abstract

A set S of vertices of a graph is a defensive k-alliance if every vertex \({v\in S}\) has at least k more neighbors in S than it has outside of S. Analogously, a set S is an offensive k-alliance if every vertex in the neighborhood of S has at least k more neighbors in S than it has outside of S. Also, a powerful k-alliance is a set S of vertices of the graph, which is both defensive k-alliance and offensive (k + 2)-alliance. A powerful k-alliance is called global if it is a dominating set. In this paper we show that for k ≥ 0, no graph is partitionable into global powerful k-alliances and, for k ≤ −1, we obtain upper bounds on the maximum number of sets belonging to a partition of a graph into global powerful k-alliances. In addition, we study the close relationships that exist between partitions of a Cartesian product graph, Γ1 × Γ2, into (global) powerful (k 1 + k 2)-alliances and partitions of Γ i into (global) powerful k i -alliances, \({i\in \{1,2\}}\).

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bermudo S., Rodríguez-Velázquez J.A., Sigarreta J.M., Yero I.G.: On global offensive k-alliances in graphs. Appl. Math. Lett. 23, 1454–1458 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  2. Brigham R.C., Dutton R., Haynes T.W., Hedetniemi S.T.: Powerful alliances in graphs. Discrete Math. 309(8), 2140–2147 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Brigham R.C., Dutton R., Hedetniemi S.: A sharp lower bound on the powerful alliance number of C m × C n . Congr. Numer. 167, 57–63 (2004)

    MathSciNet  MATH  Google Scholar 

  4. Eroh, L., Gera, R.: Alliance partition number in graphs. Ars Combin. (2007, in press)

  5. Eroh L., Gera R.: Global alliance partition in trees. J. Combin. Math. Combin. Comput. 66, 161–169 (2008)

    MathSciNet  MATH  Google Scholar 

  6. Favaron O., Fricke G., Goddard W., Hedetniemi S., Hedetniemi S.T., Kristiansen P., Laskar R.C., Skaggs R.D.: Offensive alliances in graphs. Discuss. Math. Graph Theory 24(2), 263–275 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  7. Fernau, H., Rodríguez-Velázquez, J.A., Sigarreta, J.M.: Global r-alliances and total domination. In: Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Universitá degli Studi di Milano, Gargnano, Italy. Abstracts 98–101 (2008)

  8. Fernau H., Rodríguez J.A., Sigarreta J.M.: Offensive k-alliances in graphs. Discrete Appl. Math. 157(1), 177–182 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  9. Fricke G.H., Lawson L.M., Haynes T.W., Hedetniemi S.M., Hedetniemi S.T.: A note on defensive alliances in graphs. Bull. Inst. Combin. Appl. 38, 37–41 (2003)

    MathSciNet  MATH  Google Scholar 

  10. Haynes T.W., Hedetniemi S.T., Henning M.A.: Global defensive alliances in graphs. Electron. J. Combin. 10, 139–146 (2003)

    MathSciNet  Google Scholar 

  11. Haynes T.W., Lachniet J.A.: The alliance partition number of grid graphs. AKCE Int. J. Graphs Comb. 4(1), 51–59 (2007)

    MathSciNet  MATH  Google Scholar 

  12. Kristiansen P., Hedetniemi S.M., Hedetniemi S.T.: Alliances in graphs. J. Combin. Math. Combin. Comput. 48, 157–177 (2004)

    MathSciNet  MATH  Google Scholar 

  13. Rodríguez-Velázquez J.A., González-Yero I., Sigarreta J.M.: Defensive k-alliances in graphs. Appl. Math. Lett. 22, 96–100 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  14. Rodríguez J.A., Sigarreta J.M.: Global alliances in planar graphs. AKCE Int. J. Graphs Comb. 4(1), 83–98 (2007)

    MathSciNet  MATH  Google Scholar 

  15. Rodríguez J.A., Sigarreta J.M.: Global defensive k-alliances in graphs. Discrete Appl. Math. 157, 211–218 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  16. Rodríguez J.A., Sigarreta J.M.: Offensive alliances in cubic graphs. Int. Math. Forum 1(36), 1773–1782 (2006)

    MathSciNet  MATH  Google Scholar 

  17. Rodríguez J.A., Sigarreta J.M.: Spectral study of alliances in graphs. Discuss. Math. Graph Theory 27(1), 143–157 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  18. Shafique K.H., Dutton R.D.: A tight bound on the cardinalities of maximum alliance-free and minimun alliance-cover sets. J. Combin. Math. Combin. Comput. 56, 139–145 (2006)

    MathSciNet  MATH  Google Scholar 

  19. Shafique K.H., Dutton R.D.: Maximum alliance-free and minimum alliance-cover sets. Congr. Numer. 162, 139–146 (2003)

    MathSciNet  MATH  Google Scholar 

  20. Shafique K.H., Dutton R.D.: On satisfactory partitioning of graphs. Congr. Numer. 154, 183–194 (2002)

    MathSciNet  MATH  Google Scholar 

  21. Sigarreta J.M., Rodríguez J.A.: On the global offensive alliance number of a graph. Discrete Appl. Math. 157(2), 219–226 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  22. Sigarreta J.M., Yero I.G., Bermudo S., Rodríguez-Velázquez J.A.: Partitioning a graph into offensive k-alliances. Discrete Appl. Math. 159, 224–231 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  23. Yero I.G., Bermudo S., Rodríguez-Velázquez J.A., Sigarreta J.M.: Partitioning a graph into defensive k-alliances. Acta Math. Sin. (Engl. Ser.) 27(1), 73–82 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  24. Yero, I.G., Rodríguez-Velázquez, J.A.: Boundary powerful k-alliances in graphs. Ars Combin. (2009, in press)

Download references

Author information

Authors and Affiliations

  1. Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007, Tarragona, Spain

    Ismael G. Yero & Juan A. Rodríguez-Velázquez

Authors
  1. Ismael G. Yero
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juan A. Rodríguez-Velázquez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Juan A. Rodríguez-Velázquez.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Yero, I.G., Rodríguez-Velázquez, J.A. Partitioning a Graph into Global Powerful k-Alliances. Graphs and Combinatorics 28, 575–583 (2012). https://doi.org/10.1007/s00373-011-1065-7

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-011-1065-7

Keywords

Mathematics Subject Classification (2000)

Search

Navigation