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 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 . A chapter on threshold graphs appears in , and the book is devoted to them. An equivalent definition is the following: a graph is a threshold graph if there are a real number and for each vertex a real vertex weight such that for any two vertices , is an edge if and only if . Another equivalent definition is this: a graph is a threshold graph if there are a real number and for each vertex a real vertex weight such that for any vertex set , is independent if and only if 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. 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. is always the first character of the string, and represents the first vertex of the graph. Every subsequent character is either , which denotes the addition of an isolated vertex (or union vertex), or , which denotes the addition of a dominating vertex (or join vertex). For example, the string represents a star graph with three leaves, while represents a path on three vertices.