Talk:Threshold graph
 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Equivalent definition
[edit]I think it must be "≤T" in the equivalent definition, right?
- I agree. — Preceding unsigned comment added by 130.208.240.3 (talk) 14:57, 20 March 2015 (UTC)
- It makes no difference, because this is a discrete, finite condition. Zaslav (talk) 02:36, 19 February 2016 (UTC)
Modification?
[edit]I removed the sentence "Modification to threshold graph, that is, obtaining threshold graphs is NP-complete, for all the most natural modification operations; vertex deletion, edge deletion, edge completion and edge editing." from section "Related classes of graphs and recognition" because it makes no sense. If someone can rewrite it so it says what it's supposed to, please do. Thanks. Zaslav (talk) 02:33, 19 February 2016 (UTC)
- What it means is that, given a graph that is not already a threshold graph, it's hard to find the smallest number of changes (of various types) to make it into a threshold graph. —David Eppstein (talk) 05:01, 19 February 2016 (UTC)