Graph where every connected induced subgraph has a universal vertex
Construction of a trivially perfect graph from nested intervals and from the reachability relationship in a tree
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.[1] Trivially perfect graphs were first studied by (Wolk
1962,
1965) 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,[2]arborescent comparability graphs,[3] and quasi-threshold graphs.[4]
Equivalent characterizations
Trivially perfect graphs have several other equivalent characterizations:
They are the
comparability graphs of
order-theoretic trees. That is, let T be a
partial order such that for each t ∈ T, the set {s ∈ T : s < t} is
well-ordered by the
relation<, and also T possesses a minimum element r. Then the comparability graph of T is trivially perfect, and every trivially perfect graph can be formed in this way.[5]
They are the graphs that can be represented as the
interval graphs for a set of nested
intervals. A set of intervals is nested if, for every two intervals in the set, either the two are disjoint or one contains the other.[8]
They are the graphs that are both
chordal and
cographs.[9] This follows from the characterization of chordal graphs as the graphs without induced cycles of length greater than three, and of cographs as the graphs without
induced paths on four vertices (P4).
They are the graphs that are both cographs and interval graphs.[9]
They are the graphs that can be formed, starting from one-vertex graphs, by two operations: disjoint union of two smaller trivially perfect graphs, and the addition of a new vertex adjacent to all the vertices of a smaller trivially perfect graph.[10] These operations correspond, in the underlying forest, to forming a new forest by the disjoint union of two smaller forests and forming a tree by connecting a new root node to the roots of all the trees in a forest.
They are the graphs in which, for every edge uv, the
neighborhoods of u and v (including u and v themselves) are nested: one neighborhood must be a subset of the other.[11]
The
threshold graphs are exactly the graphs that are both themselves trivially perfect and the complements of trivially perfect graphs (co-trivially perfect graphs).[14]
Chu (2008) describes a simple
linear time algorithm for recognizing trivially perfect graphs, based on
lexicographic breadth-first search. Whenever the LexBFS algorithm removes a vertex v from the first set on its queue, the algorithm checks that all remaining neighbors of v belong to the same set; if not, one of the forbidden induced subgraphs can be constructed from v. If this check succeeds for every v, then the graph is trivially perfect. The algorithm can also be modified to test whether a graph is the
complement graph of a trivially perfect graph, in linear time.
Determining if a general graph is k edge deletions away from a trivially perfect graph is
NP-complete,[15] fixed-parameter tractable[16] and can be solved in O(2.45k(m + n)) time.[17]
Nastos, James; Gao, Yong (2010), "A novel branching strategy for parameterized graph modification problems", in Wu, Weili; Daescu, Ovidiu (eds.), Combinatorial Optimization and Applications – 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18–20, 2010, Proceedings, Part II, Lecture Notes in Computer Science, vol. 6509, Springer, pp. 332–346,
arXiv:1006.3020,
doi:
10.1007/978-3-642-17461-2_27
Rubio-Montiel, C. (2015), "A new characterization of trivially perfect graphs", Electronic Journal of Graph Theory and Applications, 3 (1): 22–26,
doi:10.5614/ejgta.2015.3.1.3.
Sharan, Roded (2002), "Graph modification problems and their applications to genomic research", PhD Thesis, Tel Aviv University.
Graph where every connected induced subgraph has a universal vertex
Construction of a trivially perfect graph from nested intervals and from the reachability relationship in a tree
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.[1] Trivially perfect graphs were first studied by (Wolk
1962,
1965) 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,[2]arborescent comparability graphs,[3] and quasi-threshold graphs.[4]
Equivalent characterizations
Trivially perfect graphs have several other equivalent characterizations:
They are the
comparability graphs of
order-theoretic trees. That is, let T be a
partial order such that for each t ∈ T, the set {s ∈ T : s < t} is
well-ordered by the
relation<, and also T possesses a minimum element r. Then the comparability graph of T is trivially perfect, and every trivially perfect graph can be formed in this way.[5]
They are the graphs that can be represented as the
interval graphs for a set of nested
intervals. A set of intervals is nested if, for every two intervals in the set, either the two are disjoint or one contains the other.[8]
They are the graphs that are both
chordal and
cographs.[9] This follows from the characterization of chordal graphs as the graphs without induced cycles of length greater than three, and of cographs as the graphs without
induced paths on four vertices (P4).
They are the graphs that are both cographs and interval graphs.[9]
They are the graphs that can be formed, starting from one-vertex graphs, by two operations: disjoint union of two smaller trivially perfect graphs, and the addition of a new vertex adjacent to all the vertices of a smaller trivially perfect graph.[10] These operations correspond, in the underlying forest, to forming a new forest by the disjoint union of two smaller forests and forming a tree by connecting a new root node to the roots of all the trees in a forest.
They are the graphs in which, for every edge uv, the
neighborhoods of u and v (including u and v themselves) are nested: one neighborhood must be a subset of the other.[11]
The
threshold graphs are exactly the graphs that are both themselves trivially perfect and the complements of trivially perfect graphs (co-trivially perfect graphs).[14]
Chu (2008) describes a simple
linear time algorithm for recognizing trivially perfect graphs, based on
lexicographic breadth-first search. Whenever the LexBFS algorithm removes a vertex v from the first set on its queue, the algorithm checks that all remaining neighbors of v belong to the same set; if not, one of the forbidden induced subgraphs can be constructed from v. If this check succeeds for every v, then the graph is trivially perfect. The algorithm can also be modified to test whether a graph is the
complement graph of a trivially perfect graph, in linear time.
Determining if a general graph is k edge deletions away from a trivially perfect graph is
NP-complete,[15] fixed-parameter tractable[16] and can be solved in O(2.45k(m + n)) time.[17]
Nastos, James; Gao, Yong (2010), "A novel branching strategy for parameterized graph modification problems", in Wu, Weili; Daescu, Ovidiu (eds.), Combinatorial Optimization and Applications – 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18–20, 2010, Proceedings, Part II, Lecture Notes in Computer Science, vol. 6509, Springer, pp. 332–346,
arXiv:1006.3020,
doi:
10.1007/978-3-642-17461-2_27
Rubio-Montiel, C. (2015), "A new characterization of trivially perfect graphs", Electronic Journal of Graph Theory and Applications, 3 (1): 22–26,
doi:10.5614/ejgta.2015.3.1.3.
Sharan, Roded (2002), "Graph modification problems and their applications to genomic research", PhD Thesis, Tel Aviv University.