Elusiveness of Finding Degrees

We address the complexity of finding a vertex with specific (or maximum) (out)degree in undirected graphs, directed graphs and in tournaments in a model where we count only the probes to the adjacency matrix of the graph. Improving upon some earlier bounds, using adversary arguments, we show that the following problems require \({n \atopwithdelims ()2}\) probes to the adjacency matrix of an n node graph: determining whether a given directed graph has a vertex of outdegree k (for a non-negative integer \(k \le (n+1)/2\)); determining whether an undirected graph has a degree 0 or 1 vertex; finding the maximum (out)degree in a directed or an undirected graph, and finding all vertices with the maximum outdegree in a tournament.