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

Relating threshold tolerance graphs to other graph classes / Calamoneri, Tiziana; Sinaimeri, Blerina. - ELETTRONICO. - 1231:(2014), pp. 73-79. (Intervento presentato al convegno 16th Italian Conference on Theoretical Computer Science (ICTCS 2014) tenutosi a Perugia; Italy).

Relating threshold tolerance graphs to other graph classes

CALAMONERI, Tiziana;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
16th Italian Conference on Theoretical Computer Science (ICTCS 2014)
threshold tolerance graphs, strongly chordal graphs, leaf power graphs, min leaf power graphs
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Relating threshold tolerance graphs to other graph classes / Calamoneri, Tiziana; Sinaimeri, Blerina. - ELETTRONICO. - 1231:(2014), pp. 73-79. (Intervento presentato al convegno 16th Italian Conference on Theoretical Computer Science (ICTCS 2014) tenutosi a Perugia; Italy).
File allegati a questo prodotto
File Dimensione Formato  
Calamoneri_Relating_2014.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 312.6 kB
Formato Adobe PDF
312.6 kB Adobe PDF

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/11573/646471
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact