2018/05/24 by Emad Zahedi, Zahedi, Emad, Jason P. Smith +1
Computer Science · Mathematics · #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 · doi:10.48550/arxiv.1805.09853
openalex publication_date 2018/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G, a subgraph H is isometric if dH(u,v) = dG(u,v) for every pair u,v∈ V(H), where d is the distance function. A graph G is distance preserving (dp) if it has an isometric subgraph of every possible order. A graph is sequentially distance preserving (sdp) if its vertices can be ordered such that deleting the first i vertices results in an isometric subgraph, for all i≥1. We introduce a generalisation of the lexicographic product of graphs, which can be used to non-trivially describe graphs. This generalisation is the inverse of the modular decomposition of graphs, which divides the graph into disjoint clusters called modules. Using these operations, we give a necessary and sufficient condition for graphs to be dp. Finally, we show that the Cartesian product of a dp graph and an sdp graph is dp.