On Closed Graphs I

Abstract

A graph is closed when its vertices have a labeling by [n] with a certain property first discovered in the study of binomial edge ideals. In this article, we prove that a connected graph has a closed labeling if and only if it is chordal, claw-free, and has a property we call narrow, which holds when every vertex is distance at most one from all longest shortest paths of the graph.

The paper "On Closed Graphs" (1306.5149v1) has been divided into two papers, "On Closed Graphs I", which is this arXiv submission, and "On Closed Graphs II", which will be a separate arXiv submission