On graphs that contain exactly k copies of a subgraph, and a related problem in search theory

Gerbner, Dániel and Keszegh, Balázs and Lenger, Dániel Antal and Nagy, Dániel and Pálvölgyi, Dömötör and Patkós, Balázs and Vizer, Máté and Wiener, Gábor (2023) On graphs that contain exactly k copies of a subgraph, and a related problem in search theory. DISCRETE APPLIED MATHEMATICS, 341. pp. 196-203. ISSN 0166-218X

Preview

Text 2210.04712.pdf Download (185kB) | Preview

Abstract

We study exak(n,F), the largest number of edges in an n-vertex graph G that contains exactly k copies of a given subgraph F. The case k=0 is the Turán number ex(n,F) that is among the most studied parameters in extremal graph theory. We show that for any F and k, exak(n,F)=(1+o(1))ex(n,F)) and determine the exact values of exak(n,K3) and exa1(n,Kr) for n large enough. We also explore a connection to the following well-known problem in search theory. We are given a graph of order n that consists of an unknown copy of F and some isolated vertices. We can ask pairs of vertices as queries, and the answer tells us whether there is an edge between those vertices. Our goal is to describe the graph using as few queries as possible. Aigner and Triesch in 1990 showed that the number of queries needed is at least (n2)−exa1(n,F). Among other results we show that the number of queries that were answered NO is at least (n2)−exa1(n,F).

Actions (login required)

Edit Item