preprint · Discussiones Mathematicae Graph Theory · 2014

The smallest nonevasive graph property

Cited by 0Open access

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.

Cite this paper

APA 7

Adamaszek, M. (2014). The smallest nonevasive graph property. Discussiones Mathematicae Graph Theory, 34(4), 857. https://doi.org/10.7151/dmgt.1766

MLA 9

Adamaszek, Michał. “The smallest nonevasive graph property.” Discussiones Mathematicae Graph Theory, vol. 34, no. 4, 2014, p. 857, https://doi.org/10.7151/dmgt.1766.

Chicago

Adamaszek, Michał. 2014. “The smallest nonevasive graph property.” Discussiones Mathematicae Graph Theory 34 (4): 857. https://doi.org/10.7151/dmgt.1766.

Harvard

Adamaszek, M. (2014) ‘The smallest nonevasive graph property’, Discussiones Mathematicae Graph Theory, 34(4), p. 857. Available at: https://doi.org/10.7151/dmgt.1766.

BibTeX

@misc{adamaszek2014smallest,
  title = {{The smallest nonevasive graph property}},
  author = {Adamaszek, Michał},
  journal = {Discussiones Mathematicae Graph Theory},
  volume = {34},
  number = {4},
  pages = {857},
  year = {2014},
  doi = {10.7151/dmgt.1766}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.