A graph reconstruction problem involving common neighbors

Abstract

Given a simple graph G = (V, E) on v vertices and two distinct vertices x, y ∈ 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 vgeqslant 2 and a sequence γ of nonnegative integers arranged in non-increasing order, establish if there exists a simple graph on v vertices having γ 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₄-free graphs.

An Initial-Value Problem for an Ordinary Differential Equation Involving Multi-Term Time-Fractional Derivatives with Relaxation Factors
Fikret Gölgeleyen, Seher Seda Sarıköse Bayram, Masahiro Yamamoto
Fractal and Fractional5 Nov 2026Peer-reviewedCC BY 4.0Analysis & PDEsCrossref
Upper Bounds and Fekete–Szegö Problem for Bi-Univalent Functions Involving Bazilevič and λ-Pseudo Functions Related to Lucas-Balancing Polynomials
Shaymaa Y. Alkufi, Abbas Kareem Wanas, Alina Alb Lupas
Mathematics1 Oct 2026Peer-reviewedCC BY 4.0Geometry & topologyCrossref
A Common neighborhood signed graph of a signed graph
MUKTI ACHARYA
arXiv18 Oct 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
Solubility from a disconnected common-divisor graph on p-regular conjugacy-class sizes
Zhi-Lin Zhang
arXiv21 Oct 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Piston Problem in Common-Velocity Idealized Three-Component Models
Xiaoting Li, Lihui Guo, Huasheng Zhang
Axioms1 Sep 2026Peer-reviewedCC BY 4.0Full textGeneral mathematicsCrossrefDOAJ

Cite

BibTeX RIS

BibTeX

@misc{ascolese2026graph,
  title = {{A graph reconstruction problem involving common neighbors}},
  author = {Michela Ascolese and Pietro Negrini and Silvia Maria Carla Pagani and Marco Antonio Pellegrini},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08803},
  eprint = {2609.08803},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08803},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - A graph reconstruction problem involving common neighbors
AU  - Michela Ascolese
AU  - Pietro Negrini
AU  - Silvia Maria Carla Pagani
AU  - Marco Antonio Pellegrini
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.08803
UR  - https://arxiv.org/abs/2609.08803
AB  - Given a simple graph G = (V, E) on v vertices and two distinct vertices x, y ∈ 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 vgeqslant 2 and a sequence γ of nonnegative integers arranged in non-increasing order, establish if there exists a simple graph on v vertices having γ 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.
ER  -

Abstract

Related

Cite