The smallest nonevasive graph property

DOI10.7151/DMGT.1766zbMATH Open1303.05126arXiv1303.5601OpenAlexW2964299274MaRDI QIDQ472145FDOQ472145

Authors: Michał Adamaszek 

Publication date: 18 November 2014

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

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.

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

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

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)

Cites Work

• Combinatorial algebraic topology
• A topological approach to evasiveness
• Constructions preserving evasiveness and collapsibility
• The On-Line Encyclopedia of Integer Sequences
• A course in topological combinatorics
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• A topological approach to evasiveness
• The smallest strictly Neumaier graph and its generalisations
• Title not available (Why is that?)
• Some Results on Elusive Graph Properties
• Smallest Graphs Achieving the Stinson Bound
• A generalized model for understanding evasiveness

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)