{"id":"arxiv/2609.08803","url":"https://arxiv.org/abs/2609.08803","tags":["math.CO"],"score":0,"title":"A graph reconstruction problem involving common neighbors","domain":"math.CO","source":"arxiv","authors":["Michela Ascolese","Pietro Negrini","Silvia Maria Carla Pagani","Marco Antonio Pellegrini"],"reviews":0,"subject":"math.CO","summary":"Given a simple graph $G = (V, E)$ on $v$ vertices and two distinct vertices $x, y \\in V$, the co-degree $c_{x,y}$ associated to the pair $\\{x, y\\}$ is the number of their common neighbors in the graph $G$. The co-degree sequence of $G$, denoted by $γ(G)$, is the list of all the co-degrees associated to all the possible pairs of distinct vertices, arranged in non-increasing order. In this paper we consider the following problem, which can be viewed as a generalization of a result by Erdős and Gallai as well as of the Erdős, Rényi and Sós' friendship theorem: given an integer $v\\geqslant 2$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}