The central result is a simple parity rule for a new kind of graph convexity. Among the finite, undirected graphs that qualify as n-convex geometries, a star exists if and only if the graph has an odd number of vertices. In other words, the graph’s order—its vertex count—sets the condition for this structure.
The study introduces neighbourhood convexity, or n-convexity, as a convexity on graphs. A non-empty set of vertices is n-convex when it consists of vertices adjacent to every vertex in some witness set Y. The construction starts with a shared-neighbourhood rule: a set qualifies because all of its vertices meet the same adjacency condition relative to Y. The work concerns finite, undirected graphs and their vertex subsets.
Rules written into the class
One consequence is an exclusion rule. Every n-convex geometry is free of true twins—the paper’s term for a particular pair of vertices it excludes. The result applies to every graph that meets the paper’s definition of an n-convex geometry.
The hereditary classification is narrower still. Under the paper’s hereditary requirement, the only n-convex geometries are K1 and 2K1: a graph with one vertex and a graph with two isolated vertices. Here, “hereditary” means that the property is retained in the smaller graphs considered by the classification.
Other results put numerical limits on the class. If minimum degree means the fewest neighbours any vertex has, the number of vertices is at most twice that degree plus two. Once there are at least three vertices, the graph is connected and its diameter—the greatest shortest-path distance between two vertices—is either two or three.
The study also compares two sets of distinguished vertices, called quasi-stars and extreme vertices. It finds that their counts are equal, and that each count is at least two.
Deletion rules for the odd side
A reduction theorem describes how a star-free case can be shortened. In an n-convex geometry without stars and with at least three vertices, if x belongs to the specified set D, deleting x and its associated vertex v(x) produces an n-convex geometry without stars. The theorem’s condition on x is part of the result: it applies to x∈D.
That reduction sits alongside the paper’s sharp parity theorem, but the parity statement itself is broader: an n-convex geometry has a star exactly when its vertex count is odd. Even-order geometries therefore have no star, while odd-order geometries do.
For the odd side, the paper gives a more specific test. For a graph with an odd number of vertices, being an n-convex geometry is equivalent to having a unique star whose deletion leaves an n-convex geometry. This ties recognition of the larger graph to a single removable structure and the same neighbourhood-based condition on what remains.
Another way to read the result
A separate result recasts the picture as an ordering problem. The paper uses P(G) for a neighbourhood preorder, an ordering-like relation built from neighbourhoods. In that language, n-convex sets are upsets: if a set contains a vertex, it also contains every vertex that lies above it in the preorder. In star-free n-convex geometries, quasi-stars are maximal elements of P(G), meaning that no higher element sits above them.
The classification also links n-convex geometries with two named graph classes, threshold and quasi-threshold. For an n-convex geometry, being quasi-threshold, belonging to the set {K1, 2K1, P3}, and being threshold are equivalent. The notation names small graph forms: K1 is a one-vertex graph, 2K1 is two isolated vertices, and P3 is a three-vertex path. For any n-convex geometry with at least four vertices, the graph contains an induced P4 or C4—respectively, a four-vertex path or a four-cycle with no extra edges among the selected vertices.
The even side remains unfinished
The construction picture remains incomplete. The paper leaves open a complete method for constructing all even-order n-convex geometries. The open point is specifically a method that covers the full even-order family.
This document is an arXiv version-1 preprint dated 26 August 2026. The acknowledgements report support for Daniela Bubboloni from INdAM-GNSAGA and the PRIN 2022 project 2022PSTWLB, including CUP B53D23009410006; José Cáceres is supported by CDTIME and Junta de Andalucía under Grant FQM-425. The authors declare no conflict of interest.
Paper data and sources
Original title: The neighbourhood convexity
Authors: Daniela Bubboloni, José Cáceres
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text