Note: The Smallest Nonevasive Graph Property
A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to b...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2014-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1766 |
| _version_ | 1797713248220348416 |
|---|---|
| author | Adamaszek Michał |
| author_facet | Adamaszek Michał |
| author_sort | Adamaszek Michał |
| collection | DOAJ |
| description | A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs and show that it is essentially the unique such with n ≤ 5. |
| first_indexed | 2024-03-12T07:33:36Z |
| format | Article |
| id | doaj.art-df30aea96220427287ea2e8e618f6d95 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:33:36Z |
| publishDate | 2014-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-df30aea96220427287ea2e8e618f6d952023-09-02T21:42:47ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922014-11-0134485786210.7151/dmgt.1766dmgt.1766Note: The Smallest Nonevasive Graph PropertyAdamaszek Michał0Institute of Mathematics, University of Bremen Bibliothekstr. 1 28359 Bremen, GermanyA property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs and show that it is essentially the unique such with n ≤ 5.https://doi.org/10.7151/dmgt.1766graph propertiesevasivenesscomplexity. |
| spellingShingle | Adamaszek Michał Note: The Smallest Nonevasive Graph Property Discussiones Mathematicae Graph Theory graph properties evasiveness complexity. |
| title | Note: The Smallest Nonevasive Graph Property |
| title_full | Note: The Smallest Nonevasive Graph Property |
| title_fullStr | Note: The Smallest Nonevasive Graph Property |
| title_full_unstemmed | Note: The Smallest Nonevasive Graph Property |
| title_short | Note: The Smallest Nonevasive Graph Property |
| title_sort | note the smallest nonevasive graph property |
| topic | graph properties evasiveness complexity. |
| url | https://doi.org/10.7151/dmgt.1766 |
| work_keys_str_mv | AT adamaszekmichał notethesmallestnonevasivegraphproperty |