Let G be the graph obtained as the edge intersection of two graphs G1, G2 on the same vertex set V. We show that if at least one of G1, G2 is perfect, then α(G) <= α(G1)·α(G2), where α() is the cardinality of the largest stable set. Moreover, for general G1 and G2, we show that α(G) <= R(α(G1)+1,α(G2)+1)−1, where R(k,l) is the Ramsey number.

On the Stability Number of the Edge Intersection of Two Graphs

ARBIB, CLAUDIO;
2002-01-01

Abstract

Let G be the graph obtained as the edge intersection of two graphs G1, G2 on the same vertex set V. We show that if at least one of G1, G2 is perfect, then α(G) <= α(G1)·α(G2), where α() is the cardinality of the largest stable set. Moreover, for general G1 and G2, we show that α(G) <= R(α(G1)+1,α(G2)+1)−1, where R(k,l) is the Ramsey number.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/1053
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact