Download PDF - On -independence in graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On -independence in graphs

Authors 1, 2, 2, 3

Affiliations

  1. Fakultät für Mathematik, TU Chemnitz, 09107 Chemnitz, Germany
  2. Institut für Mathematik, TU Ilmenau, Postfach 100565, 98684 Ilmenau, Germany
  3. Institut für Diskrete Mathematik und Algebra, TU Bergakademie Freiberg, 09596 Freiberg, Germany

Abstract

Let be a set of graphs and for a graph G let α(G) and α⋅(G) denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on α(G) and α⋅(G) are presented.

Keywords

ENG
independence, complexity, probabilistic method

Bibliography

  1. N. Alon and J.H. Spencer, The probablilistic method (2nd ed.), (Wiley, 2000), doi: 10.1002/0471722154.
  2. R. Boliac, C. Cameron and V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin. 72 (2004) 241-253.
  3. M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
  4. M. Borowiecki, D. Michalak and E. Sidorowicz, Generalized domination, independence and irredudance in graphs, Discuss. Math. Graph Theory 17 (1997) 147-153, doi: 10.7151/dmgt.1048.
  5. Y. Caro, New results on the independence number, Technical Report (Tel-Aviv University, 1979).
  6. Y. Caro and Y. Roditty, On the vertex-independence number and star decomposition of graphs, Ars Combin. 20 (1985) 167-180.
  7. G. Chartrand, D. Geller and S. Hedetniemi, Graphs with forbiden subgraphs, J. Combin. Theory 10 (1971) 12-41, doi: 10.1016/0095-8956(71)90065-7.
  8. G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman & Hall, 2005).
  9. M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman and Company, San Francisco, 1979).
  10. J. Harant, A. Pruchnewski and M. Voigt, On Dominating Sets and Independendent Sets of Graphs, Combinatorics, Probability and Computing 8 (1999) 547-553, doi: 10.1017/S0963548399004034.
  11. S. Hedetniemi, On hereditary properties of graphs, J. Combin. Theory (B) 14 (1973) 349-354, doi: 10.1016/S0095-8956(73)80009-7.
  12. V. Vadim and D. de Werra, Special issue on stability in graphs and related topics, Discrete Appl. Math. 132 (2003) 1-2, doi: 10.1016/S0166-218X(03)00385-8.
  13. Zs. Tuza, Lecture at Conference of Hereditarnia (Zakopane, Poland, September 2006).
  14. V.K. Wei, A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum 81-11217-9 (Murray Hill, NJ, 1981).
Discussiones Mathematicae Graph Theory
2009/29/2
Export to PBN, Opens in new tab
Pages:
377-383
Main language of publication
English
Received
2008-03-25
Accepted
2008-03-26
Published
2009

DOI: 10.7151/dmgt.1453

Exact and natural sciences