A graph reconstruction problem involving common neighbors

Abstract

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 $\gamma (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⩾2$ and a sequence $\gamma$ of nonnegative integers arranged in non-increasing order, establish if there exists a simple graph on $v$ vertices having $\gamma$ as its co-degree sequence and, in case of positive answer, provide such a graph. We provide a full answer to this problem for the class of planar $C_4$-free graphs.