The Interval function, Ptolemaic, distance hereditary, bridged graphs and axiomatic characterizations

2020/05/14 by Manoj Changat, Changat, Manoj, Lekshmi Kamal K. Sheela +3
Computer Science · Mathematics · #05C12 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2005.06751

openalex publication_date 2020/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we consider certain types of betweenness axioms on the interval function I_G of a connected graph G. We characterize the class of graphs for which I_G satisfy these axioms. The class of graphs that we characterize include the important class of Ptolemaic graphs and some proper superclasses of Ptolemaic graphs: the distance hereditary graphs and the bridged graphs. We also provide axiomatic characterizations of the interval function of these classes of graphs using an arbitrary function known as transit function.

Related

• Weakly modular graphs with diamond condition, the interval function and axiomatic characterizations
• The Toll Walk Transit Function of a Graph: Axiomatic Characterizations and First-Order Non-definability
• Directed Transit Functions
• Graph limits and hereditary properties
• Interval k-Graphs and Orders