Threshold graph

Last updated January 30, 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:

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.

Related Research Articles

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

<span class="mw-page-title-main">Component (graph theory)</span> Maximal subgraph whose vertices can reach each other

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

In the mathematical field of graph theory, the complement or inverse of a graph $G$ is a graph $H$ on the same vertices such that two distinct vertices of $H$ are adjacent if and only if they are not adjacent in $G$ . That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ and is closed under complementation and disjoint union.

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if some combinatorial structure S satisfies some property P, or is "far" from having this property, using only a small number of "local" queries to the object.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

In graph theory, the tree-depth of a connected undirected graph $is a numerical invariant of, the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.$

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.

In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows.

In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph.

In graph theory, the graph removal lemma states that when a graph contains few copies of a given subgraph, then all of the copies can be eliminated by removing a small number of edges. The special case in which the subgraph is a triangle is known as the triangle removal lemma.

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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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]