The smallest nonevasive graph property

DOI10.7151/DMGT.1766MaRDI QIDQ472145zbMATH OpenOpenAlexFDO

Authors Michał Adamaszek

Publication date 18 November 2014

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1303.5601

zbMATH Keywords

complexitygraph propertiesevasiveness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Graph theory (05C99) Discrete-time games (91A50)

Abstract: 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 at most 5.

Recommendations

• A generalized model for understanding evasiveness
• A topological approach to evasiveness
• scientific article; zbMATH DE number 3902707
• Searching for an edge in a graph
• Monotone Bipartite Graph Properties are Evasive

Cites work

• scientific article; zbMATH DE number 3460321 (Why is no real title available?)
• scientific article; zbMATH DE number 3617539 (Why is no real title available?)
• A course in topological combinatorics
• A topological approach to evasiveness
• Combinatorial algebraic topology
• Constructions preserving evasiveness and collapsibility
• The On-Line Encyclopedia of Integer Sequences

Cited in

(7)

• A topological approach to evasiveness
• The evasiveness conjecture and graphs on \(2p\) vertices
• The smallest strictly Neumaier graph and its generalisations
• scientific article; zbMATH DE number 4003527 (Why is no real title available?)
• Some Results on Elusive Graph Properties
• Smallest Graphs Achieving the Stinson Bound
• A generalized model for understanding evasiveness

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: The smallest nonevasive graph property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472145)