On 𝓕-independence in graphs

Frank Göring; Jochen Harant; Dieter Rautenbach; Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 2, page 377-383
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Frank Göring, et al. "On 𝓕-independence in graphs." Discussiones Mathematicae Graph Theory 29.2 (2009): 377-383. <http://eudml.org/doc/270163>.

@article{FrankGöring2009,
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.},
author = {Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {independence; complexity; probabilistic method},
language = {eng},
number = {2},
pages = {377-383},
title = {On 𝓕-independence in graphs},
url = {http://eudml.org/doc/270163},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Frank Göring
AU - Jochen Harant
AU - Dieter Rautenbach
AU - Ingo Schiermeyer
TI - On 𝓕-independence in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 2
SP - 377
EP - 383
AB - 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.
LA - eng
KW - independence; complexity; probabilistic method
UR - http://eudml.org/doc/270163
ER -

References

top
  1. [1] N. Alon and J.H. Spencer, The probablilistic method (2nd ed.), (Wiley, 2000), doi: 10.1002/0471722154. 
  2. [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. Zbl1075.05066
  3. [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. Zbl0902.05026
  4. [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. Zbl0904.05045
  5. [5] Y. Caro, New results on the independence number, Technical Report (Tel-Aviv University, 1979). 
  6. [6] Y. Caro and Y. Roditty, On the vertex-independence number and star decomposition of graphs, Ars Combin. 20 (1985) 167-180. Zbl0623.05031
  7. [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. Zbl0223.05101
  8. [8] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman & Hall, 2005). Zbl1057.05001
  9. [9] M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman and Company, San Francisco, 1979). 
  10. [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. Zbl0959.05080
  11. [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. [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. Zbl1028.01503
  13. [13] Zs. Tuza, Lecture at Conference of Hereditarnia (Zakopane, Poland, September 2006). 
  14. [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). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.