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

complexityevasivenessgraph properties

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph theory (05C99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) 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

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

Cited in

(7)

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

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)