Threshold graph: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 17:40, 29 January 2023

In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:

Addition of a single isolated vertex to the graph.
Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.

For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered.

Threshold graphs were first introduced by Chvátal & Hammer (1977). A chapter on threshold graphs appears in Golumbic (1980), and the book Mahadev & Peled (1995) is devoted to them.

Alternative definitions

An equivalent definition is the following: a graph is a threshold graph if there are a real number $S$ and for each vertex $v$ a real vertex weight $w(v)$ such that for any two vertices $v,u$ , $uv$ is an edge if and only if $w(u)+w(v)>S$ .

Another equivalent definition is this: a graph is a threshold graph if there are a real number $T$ and for each vertex $v$ a real vertex weight $a(v)$ such that for any vertex set $X\subseteq V$ , $X$ is independent if and only if $\sum _{v\in X}a(v)\leq T.$

The name "threshold graph" comes from these definitions: S is the "threshold" for the property of being an edge, or equivalently T is the threshold for being independent.

Threshold graphs also have a forbidden graph characterization: A graph is a threshold graph if and only if it no four of its vertices form an induced subgraph that is a three-edge path graph, a four-edge cycle graph, or a two-edge matching.

Decomposition

From the definition which uses repeated addition of vertices, one can derive an alternative way of uniquely describing a threshold graph, by means of a string of symbols. $\epsilon$ is always the first character of the string, and represents the first vertex of the graph. Every subsequent character is either $u$ , which denotes the addition of an isolated vertex (or union vertex), or $j$ , which denotes the addition of a dominating vertex (or join vertex). For example, the string $\epsilon uuj$ represents a star graph with three leaves, while $\epsilon uj$ represents a path on three vertices. The graph of the figure can be represented as $\epsilon uuujuuj$

Related classes of graphs and recognition

Threshold graphs are a special case of cographs, split graphs, and trivially perfect graphs. A graph is a threshold graph if and only if it is both a cograph and a split graph. Every graph that is both a trivially perfect graph and the complementary graph of a trivially perfect graph is a threshold graph. Threshold graphs are also a special case of interval graphs. All these relations can be explained in terms of their characterisation by forbidden induced subgraphs. A cograph is a graph with no induced path on four vertices, P₄, and a threshold graph is a graph with no induced P₄, C₄ nor 2K₂. C₄ is a cycle of four vertices and 2K₂ is its complement, that is, two disjoint edges. This also explains why threshold graphs are closed under taking complements; the P₄ is self-complementary, hence if a graph is P₄-, C₄- and 2K₂-free, its complement is as well.

Heggernes & Kratsch (2007) showed that threshold graphs can be recognized in linear time; if a graph is not threshold, an obstruction (one of P₄, C₄, or 2K₂) will be output.

References

^ Reiterman, Jan; Rödl, Vojtěch; Šiňajová, Edita; Tůma, Miroslav (1985-04-01). "Threshold hypergraphs". Discrete Mathematics. 54 (2): 193–200. doi:10.1016/0012-365X(85)90080-9. ISSN 0012-365X.

Chvátal, Václav; Hammer, Peter L. (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L.; Korte, B. H.; et al. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, pp. 145–162.
Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press. 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004.
Heggernes, Pinar; Kratsch, Dieter (2007), "Linear-time certifying recognition algorithms and forbidden induced subgraphs" (PDF), Nordic Journal of Computing, 14 (1–2): 87–108 (2008), MR 2460558.
Mahadev, N. V. R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, Elsevier.

External links

Threshold graphs, Information System on Graph Classes and their Inclusions.

[1] Reiterman, Jan; Rödl, Vojtěch; Šiňajová, Edita; Tůma, Miroslav (1985-04-01). "Threshold hypergraphs". Discrete Mathematics. 54 (2): 193–200. doi:10.1016/0012-365X(85)90080-9. ISSN 0012-365X.

[1]

@@ Line 1: / Line 1: @@
+{{Short description|Graph formed by adding isolated or universal vertices}}
 [[Image:threshold graph.png|thumb|upright=1.2|An example of a threshold graph.]]
 In [[graph theory]], a '''threshold graph''' is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:
-#Addition of a single isolated vertex to the graph.
+# Addition of a single isolated vertex to the graph.
-#Addition of a single [[dominating vertex]] to the graph, i.e. a single vertex that is connected to all other vertices.
+# Addition of a single [[dominating vertex]] to the graph, i.e. a single vertex that is connected to all other vertices.
 For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered.
@@ Line 8: / Line 9: @@
 Threshold graphs were first introduced by {{harvtxt|Chvátal|Hammer|1977}}. A chapter on threshold graphs appears in {{harvtxt|Golumbic|1980}}, and the book {{harvtxt|Mahadev|Peled|1995}} is devoted to them.
-== Alternative definitions ==
+==Alternative definitions==
+An equivalent definition is the following: a graph is a threshold graph if there are a real number <math>S</math> and for each [[Vertex (graph theory)|vertex]] <math>v</math> a real vertex weight <math>w(v)</math> such that for any two vertices <math>v,u</math>, <math>uv</math> is an [[Glossary of graph theory#edge|edge]] if and only if <math>w(u)+w(v)> S</math>.
-An equivalent definition is the following: a graph is a threshold graph if there are a real number <math>S</math> and for each [[Vertex_(graph_theory)|vertex]] <math>v</math> a real vertex weight <math>w(v)</math> such that for any two vertices <math>v,u</math>, <math>uv</math> is an [[Glossary_of_graph_theory#edge|edge]] if and only if <math>w(u)+w(v)> S</math>.
 <!-- To see why the two definition are equivalent, observe that a graph constructed using the first definition is also a graph of the second definition by setting <math>S=1</math>, <math>w(u)=1</math> for vertices that were added as dominating vertices and <math>w(u)=0</math> for all other vertices. For the other direction, given <math>S</math> and <math>w</math> we can construct the same graph by starting with the graph whose only vertex is the vertex with the minimum weight and then examining all remaining vertices in order of non-decreasing weight. Each one is added as a -->
-Another equivalent definition is this:  a graph is a threshold graph if there are a real number <math>T</math> and for each vertex <math>v</math> a real vertex weight <math>a(v)</math> such that for any vertex set <math>X\subseteq V</math>, <math>X</math> is [[Independent_set_(graph_theory)|independent]] if and only if <math>\sum_{v \in X} a(v) \le T.</math>
+Another equivalent definition is this:  a graph is a threshold graph if there are a real number <math>T</math> and for each vertex <math>v</math> a real vertex weight <math>a(v)</math> such that for any vertex set <math>X\subseteq V</math>, <math>X</math> is [[Independent set (graph theory)|independent]] if and only if <math>\sum_{v \in X} a(v) \le T.</math>
 The name "threshold graph" comes from these definitions: ''S'' is the "threshold" for the property of being an edge, or equivalently ''T'' is the threshold for being independent.
+Threshold graphs also have a [[forbidden graph characterization]]: A graph is a threshold graph if and only if it no four of its vertices form an [[induced subgraph]] that is a three-edge [[path graph]], a four-edge [[cycle graph]], or a two-edge [[matching (graph theory)|matching]].
 ==Decomposition==
@@ Line 21: / Line 23: @@
 ==Related classes of graphs and recognition==
-Threshold graphs are a special case of [[cograph]]s, [[split graph]]s, and [[trivially perfect graph]]s.  Every graph that is both a cograph and a split graph is a threshold graph.  Every graph that is both a trivially perfect graph and the [[Complement graph|complementary graph]] of a trivially perfect graph is a threshold graph. Threshold graphs are also a special case of [[interval graph]]s.  All these relations can be explained in terms of their characterisation by forbidden induced subgraphs.  A cograph is a graph with no induced path on four vertices, P<sub>4</sub>, and a threshold graph is a graph with no induced P<sub>4</sub>, C<sub>4</sub> nor 2K<sub>2</sub>.  C<sub>4</sub> is a cycle of four vertices and 2K<sub>2</sub> is its complement, that is, two disjoint edges.  This also explains why threshold graphs are closed under taking complements; the P<sub>4</sub> is self-complementary, hence if a graph is P<sub>4</sub>-, C<sub>4</sub>- and 2K<sub>2</sub>-free, its complement is as well.
+Threshold graphs are a special case of [[cograph]]s, [[split graph]]s, and [[trivially perfect graph]]s. A graph is a threshold graph if and only if it is both a cograph and a split graph.  Every graph that is both a trivially perfect graph and the [[Complement graph|complementary graph]] of a trivially perfect graph is a threshold graph. Threshold graphs are also a special case of [[interval graph]]s.  All these relations can be explained in terms of their characterisation by forbidden induced subgraphs.  A cograph is a graph with no induced path on four vertices, P<sub>4</sub>, and a threshold graph is a graph with no induced P<sub>4</sub>, C<sub>4</sub> nor 2K<sub>2</sub>.  C<sub>4</sub> is a cycle of four vertices and 2K<sub>2</sub> is its complement, that is, two disjoint edges.  This also explains why threshold graphs are closed under taking complements; the P<sub>4</sub> is self-complementary, hence if a graph is P<sub>4</sub>-, C<sub>4</sub>- and 2K<sub>2</sub>-free, its complement is as well.
 {{harvtxt|Heggernes|Kratsch|2007}} showed that threshold graphs can be recognized in linear time; if a graph is not threshold, an obstruction (one of P<sub>4</sub>, C<sub>4</sub>, or 2K<sub>2</sub>) will be output.
 ==See also==
-*[[Indifference graph]]
+* [[Indifference graph]]
-*[[Series-parallel graph]]
+* [[Series–parallel graph]]
+*Threshold hypergraphs<ref>{{Cite journal|last1=Reiterman|first1=Jan|last2=Rödl|first2=Vojtěch|last3=Šiňajová|first3=Edita|last4=Tůma|first4=Miroslav|date=1985-04-01|title=Threshold hypergraphs|url=https://dx.doi.org/10.1016/0012-365X%2885%2990080-9|journal=Discrete Mathematics|language=en|volume=54|issue=2|pages=193–200|doi=10.1016/0012-365X(85)90080-9|issn=0012-365X|doi-access=free}}</ref>
 ==References==
+{{Reflist}}
 *{{citation
  | last1 = Chvátal | first1 = Václav | author1-link = Václav Chvátal
@@ Line 54: / Line 58: @@
  | last1 = Heggernes | first1 = Pinar | author1-link = Pinar Heggernes
  | last2 = Kratsch | first2 = Dieter
- | issue = 1-2
+ | issue = 1–2
  | journal = Nordic Journal of Computing
  | mr = 2460558