“Trivially perfect graph”的意思、由来-开放百科全书

词条

Trivially perfect graph

释义

Equivalent characterizations
Related classes of graphs
Recognition
Notes
References
External links

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 {{harvs|last=Wolk|year=1962|year2=1965}} but were named by {{harvtxt|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 do not have a P₄ path graph or a C₄ cycle graph as induced subgraphs.^[6]
They are the graphs in which every connected induced subgraph contains a universal vertex.{{sfnp|Wolk|1962}}
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.^[7]
They are the graphs that are both chordal and cographs.^[8] 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 (P₄).
They are the graphs that are both cographs and interval graphs.^[8]
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.^[9] 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.^[10]
They are the permutation graphs defined from stack-sortable permutations.^[11]
They are the graphs with the property that in each of its induced subgraphs the clique cover number equals the number of maximal cliques.{{sfnp|Rubio-Montiel|2015}}
They are the graphs with the property that in each of its induced subgraphs the clique number equals the pseudo-Grundy number.{{sfnp|Rubio-Montiel|2015}}
They are the graphs with the property that in each of its induced subgraphs the chromatic number equals the pseudo-Grundy number.{{sfnp|Rubio-Montiel|2015}}

Related classes of graphs

It follows from the equivalent characterizations of trivially perfect graphs that every trivially perfect graph is also a cograph, a chordal graph, a Ptolemaic graph, an interval graph, and a perfect graph.

The threshold graphs are exactly the graphs that are both themselves trivially perfect and the complements of trivially perfect graphs (co-trivially perfect graphs).^[12]

Windmill graphs are trivially perfect.

Recognition

{{harvtxt|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,{{sfnp|Sharan|2002}} fixed-parameter tractable{{sfnp|Cai|1996}} and can be solved in O(2.45^k(m + n)) time.{{sfnp|Nastos|Gao|2010}}

Notes

1. ^{{harvtxt|Brandstädt|Le|Spinrad|1999}}, definition 2.6.2, p.34; {{harvtxt|Golumbic|1978}}.
2. ^{{harvtxt|Wolk|1962}}; {{harvtxt|Wolk|1965}}.
3. ^{{harvtxt|Donnelly|Isaak|1999}}.
4. ^{{harvtxt|Yan|Chen|Chang|1996}}.
5. ^{{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.6.1, p. 99; {{harvtxt|Golumbic|1978}}, corollary 4.
6. ^{{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.6.1, p. 99; {{harvtxt|Golumbic|1978}}, theorem 2. {{harvtxt|Wolk|1962}} and {{harvtxt|Wolk|1965}} proved this for comparability graphs of rooted forests.
7. ^{{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 51.
8. ^¹{{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 248; {{harvtxt|Yan|Chen|Chang|1996}}, theorem 3.
9. ^{{harvtxt|Yan|Chen|Chang|1996}}; {{harvtxt|Gurski|2006}}.
10. ^{{harvtxt|Yan|Chen|Chang|1996}}, theorem 3.
11. ^{{harvtxt|Rotem|1981}}.
12. ^{{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.6.3, p. 100; {{harvtxt|Golumbic|1978}}, corollary 5.

References

{{citation

| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt
| last2 = Le | first2 = Van Bang | last3 = Spinrad | first3 = Jeremy
| title = Graph Classes: A Survey
| publisher = SIAM Monographs on Discrete Mathematics and Applications
| year = 1999
| isbn = 0-89871-432-X}}.

{{Citation

| last1=Cai | first1=L. | author1-link=Leizhen Cai
| title=Fixed-parameter tractability of graph modification problems for hereditary properties
| doi=10.1016/0020-0190(96)00050-6
| year=1996
| journal=Information Processing Letters
| volume=58
| pages=171–176
| issue=4}}.

{{citation

| last = Chu | first = Frank Pok Man
| doi = 10.1016/j.ipl.2007.12.009
| issue = 1
| journal = Information Processing Letters
| pages = 7–12
| title = A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
| volume = 107
| year = 2008}}.

{{citation

| last1 = Donnelly | first1 = Sam
| last2 = Isaak | first2 = Garth
| doi = 10.1016/S0012-365X(98)00346-X
| issue = 1-3
| journal = Discrete Mathematics
| pages = 33–44
| title = Hamiltonian powers in threshold and arborescent comparability graphs
| volume = 202
| year = 1999}}

{{citation

| last = Golumbic | first = Martin Charles | authorlink = Martin Charles Golumbic
| doi = 10.1016/0012-365X(78)90178-4
| issue = 1
| journal = Discrete Mathematics
| pages = 105–107
| title = Trivially perfect graphs
| volume = 24
| year = 1978}}.

{{citation

| last = Gurski | first = Frank
| doi = 10.1016/j.disc.2005.11.014
| issue = 2
| journal = Discrete Mathematics
| pages = 271–277
| title = Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
| volume = 306
| year = 2006}}.

{{Citation

| last1 = Nastos | first1=James | last2=Gao | first2=Yong
| title=A Novel Branching Strategy for Parameterized Graph Modification Problems
| journal= Lecture Notes in Computer Science
| volume=6509
| pages=332–346
| year = 2010}}.

{{citation

| last = Rotem | first = D.
| doi = 10.1016/0012-365X(81)90165-5
| issue = 2
| journal = Discrete Mathematics
| mr = 599081
| pages = 185–196
| title = Stack sortable permutations
| volume = 33
| year = 1981}}.

{{citation

| last = Rubio-Montiel | first = C.
| doi = 10.5614/ejgta.2015.3.1.3
| issue = 1
| journal = Electronic Journal of Graph Theory and Applications
| pages = 22–26
| title = A new characterization of trivially perfect graphs
| volume = 3
| year = 2015}}.

{{citation

| last = Sharan | first = Roded
| journal = PhD Thesis, Tel Aviv University
| title = Graph modification problems and their applications to genomic research
| year = 2002}}.

{{citation

| last = Wolk | first = E. S.
| doi = 10.1090/S0002-9939-1962-0172273-0
| edition = 5
| journal = Proceedings of the American Mathematical Society
| pages = 789–795
| title = The comparability graph of a tree
| volume = 13
| year = 1962}}.

{{citation

| last = Wolk | first = E. S.
| doi = 10.1090/S0002-9939-1965-0172274-5
| edition = 1
| journal = Proceedings of the American Mathematical Society
| pages = 17–20
| title = A note on the comparability graph of a tree
| volume = 16
| year = 1965}}.

{{citation

| last1 = Yan | first1 = Jing-Ho
| last2 = Chen | first2 = Jer-Jeong
| last3 = Chang | first3 = Gerard J.
| doi = 10.1016/0166-218X(96)00094-7
| issue = 3
| journal = Discrete Applied Mathematics
| pages = 247–255
| title = Quasi-threshold graphs
| volume = 69
| year = 1996}}.{{refend}}

External links

{{citation

| contribution-url = http://www.graphclasses.org/classes/gc_327.html
| contribution = Trivially perfect graphs
| url = http://www.graphclasses.org/classes/gc_327.html
| title = Information System on Graph Classes and their Inclusions}}

2 : Graph families|Perfect graphs

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。