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