A graph G=(V, E) is a threshold tolerance if it is possible to associate weights and tolerances with each node of G so that two nodes are adjacent exactly when the sum of their weights exceeds either one of their tolerances. Threshold tolerance graphs are a special case of the well-known class of tolerance graphs and generalize the class of threshold graphs which are also extensively studied in literature. In this note we relate the threshold tolerance graphs with other important graph classes. In particular we show that threshold tolerance graphs are a proper subclass of co-strongly chordal graphs and strictly include the class of co-interval graphs. To this purpose, we exploit the relation with another graph class, min leaf power graphs (mLPGs).

Calamoneri, Tiziana; Sinaimeri, Blerina. (2014). Relating threshold tolerance graphs to other graph classes. In Proc. 16th Italian Conference on Theoretical Computer Science (ICTCS 2014) (pp. 73- 79). https://ceur-ws.org/Vol-1231/.

Relating threshold tolerance graphs to other graph classes

SINAIMERI, BLERINA
2014

Abstract

A graph G=(V, E) is a threshold tolerance if it is possible to associate weights and tolerances with each node of G so that two nodes are adjacent exactly when the sum of their weights exceeds either one of their tolerances. Threshold tolerance graphs are a special case of the well-known class of tolerance graphs and generalize the class of threshold graphs which are also extensively studied in literature. In this note we relate the threshold tolerance graphs with other important graph classes. In particular we show that threshold tolerance graphs are a proper subclass of co-strongly chordal graphs and strictly include the class of co-interval graphs. To this purpose, we exploit the relation with another graph class, min leaf power graphs (mLPGs).
2014
threshold tolerance graphs; strongly chordal graphs; leaf power graphs; min leaf power graphs
Calamoneri, Tiziana; Sinaimeri, Blerina. (2014). Relating threshold tolerance graphs to other graph classes. In Proc. 16th Italian Conference on Theoretical Computer Science (ICTCS 2014) (pp. 73- 79). https://ceur-ws.org/Vol-1231/.
File in questo prodotto:
File Dimensione Formato  
Calamoneri_Relating_2014.pdf

Open Access

Tipologia: Versione dell'editore
Licenza: Copyright dell'editore (accesso aperto)
Dimensione 312.6 kB
Formato Adobe PDF
312.6 kB Adobe PDF Visualizza/Apri
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/11385/253904
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex 4
social impact