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).
In the literature, there exist hundreds of graph classes (for an idea of the variety and
the extent of this, see [
A graph G = (V, E) is a threshold tolerance graph 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 of their tolerances. More formally, there
are positive real-valued functions, weights g and tolerances t on V such that {x, y} ∈ E
if and only if g(x) + g(y) ≥ min (t(x), t(y)). In the following we denote by TT the class
? This work was supported in part by the Italian Ministry of Education, University, and Research
(MIUR) under PRIN 2012C4E3KT national research project “AMANDA’ - Algorithmics for
MAssive and Networked DAta”
of threshold tolerance graphs and indicate with G = (V, E, g, t) a graph in this class.
Threshold tolerance graphs have been introduced in [
A chord of a cycle is an edge between two non consecutive vertices x, y of the cycle. A chord between two vertices x, y in an even cycle C is odd, when the distance in C between x and y is odd. A graph is chordal if every cycle of length at least 4 has a chord.
A graph is strongly chordal if it is chordal and every cycle of even length at least 6 has an odd chord.
Strongly chordal graphs can be also characterized in terms of excluding subgraphs. A k-sun (also known as trampoline), for k ≥ 3, is the graph on 2k vertices obtained from a clique {c1, . . . , ck} on k vertices and an independent set {s1, . . . , sk} on k vertices and edge {si, ci}, {si, ci+1} for all 1 ≤ i < k, and {sk, ck}, {sk, c1}.
A graph is strongly chordal if and only if it does not contain either a cycle on at least
4 vertices or a k-sun as an induced subgraph [
A graph is co-strongly chordal if its complement is a strongly chordal graph.
It is known [
We provide a graph that belongs to the class of co-strongly chordal graphs but not to the class of threshold tolerance graphs, so proving that these two classes do not coincide.
A graph is a tolerance graph [
A graph is an interval graph if it has an intersection model consisting of intervals on a straight line. Clearly interval graphs are included in tolerance graphs and can be obtained by fixing a constant tolerance function. We will call Int the class of interval graphs.
It is known that co-Tol includes TT and that TT includes co-Int; while it can be easily
derived that co-Tol properly includes TT, it is not known whether the other inclusion
is strict or not (again, in ISGCI [
In order to prove that TT is properly included in co-SC, we need to introduce the classes of leaf power graphs (LPG) and min leaf power graphs (mLPG).
A graph G(V, E) is a leaf power graph [
A t-caterpillar is a tree in which all the nodes are within distance 1 of a central path, called spine, constituted of t nodes.
Although there has been a lot of work on this class of graphs (for a survey on this
topic see e.g. [
The following result is particularly relevant for our reasoning.
Fact 1 [
The class mLPG is defined similarly to the class of leaf power graphs reversing the
inequality in the definition. Formally, a graph G = (V, E) is a min leaf power graph
(mLPG) [
In [
The next result will be useful in the following.
Fact 2 [
The main issue related to LPG and mLPG is to prove that a certain class belongs to them by providing a constructive method that, given a graph, defines tree T , edgeweight function w and value dmin or dmax.
In the next section we will prove that threshold tolerance graphs are mLPGs and use this fact to separate the class TT from other graph classes. 3
Before proving the main result of this section, i.e. that threshold tolerance graphs are mLPGs, we need to demonstrate a preliminary lemma stating that, when we deal with threshold tolerance graphs, w.l.o.g. we can restrict ourselves to the case when g and t take only positive integer values.
Lemma 1. A graph G = (V, E) is a threshold tolerance if and only if there exist two functions g, t : V → N+ such that (V, E, g, t) is threshold tolerance. integer.
Proof. Clearly if f , g exist then by definitionG is a threshold tolerance graph. Suppose now G is a threshold tolerance graph which weight and tolerance functions g and t are both defined fromV to R+. We show that nevertheless, it is not restrictive to assume that g, t : V → Q+ in view of the density of rational numbers among real numbers. So, we can assume that, for each v ∈ V, t(v) = nv/dv. Let m be the minimum common multiple of all the numbers dv, v ∈ V. So we can express t(v) as t(v) = nv·m/dv where m/dv is an m
Define now the new functionsg0 and t0 as g0(v) = g(v) · m and t0(v) = t(v) · m, v ∈ V. Clearly, it holds that g0 : V → Q+ while t0 : V → N+.
In order to prove the claim, it remains to prove that g0 and t0 define the same graph min(t(x), t(y)) · m = min(t0(x), t0(y)) if and only if g(x) + g(y) ≥ min(t(x), t(y)). defined byt and g. This descends from the fact that g0(x) + g0(y) = (g(x) + g(y)) · m ≥ tu Theorem 1. Threshold tolerance graphs are mLPGs.
g(v) + K−t(v) .
2 Proof. Let G = (V, E, g, t) be a threshold tolerance graph. Let K = maxv t(v). In view of Lemma 1, it is not restrictive to assume that g : V → N+, so we split the nodes of G in groups S 1, . . . , S K such that S i = {v ∈ V(G) : t(v) = i}. Observe that for some values of i the set S i can be empty. We associate to G a caterpillar T as in Figure 2.
The spine of the caterpillar is formed by K nodes, x1, . . . , xK , and each node xi is connected to the leaves lv corresponding to nodes v in S i. The weights w of the edges of T are defined as follows: − For each edge of the spine w(xi, xi+1) = 0.5 for 0 ≤ i ≤ K − 1. − For each leaf lv connected to the spine through node xi we assign a weight w(v, xi) = t(u) = min (t(u), t(v)). We have that
We show that G = mLPG(T, w, K). To this purpose consider two nodes u and v in G. By construction, in T we have that lu is connected to xt(u) and lv to xt(v), where t(u) and t(v) are not necessary distinct. Clearly, w.l.o.g we can assume t(v) ≥ t(u), i.e.
Clearly, dT (lu, lv) ≥ K if and only if g(u) + g(v) ≥ t(u) = min (t(u), t(v)) and this Now we are ready to prove the following Theorem.
Proof. Observe that according to the previous facts, T T are included in mLPG which in turn is strictly included in co-strongly chordal class of graphs. This proves the claim. tu tu (a)
(b)
It is known [
It is easy to see that the graph S 3 belongs to the class of split antimatchings that
are provably included in LPG but not in mLPG [
These inclusions prove the following: Theorem 3. The classes T T \ LPG and co-TT \mLPG are not empty.
Collecting these results and those reported in [
In this paper, we clarified the relation between some classes of graphs. In particular,
we have been able to position some special graphs, in order to prove that some class
inclusions are strict. In particular, we proved that threshold tolerance graphs are strictly
included in co-strongly chordal graphs, so confuting a conjecture reported in [
We summarize the obtained results in the two diagrams of Figure 4, from which it naturally arises an interesting open problem: how are related tolerance graphs and leaf power graphs (and, analogously, co-tolerance and min leaf power graphs)?