Distance preserving graphs and graph products.

zbMATH Open1488.05159arXiv1507.04800MaRDI QIDQ4683301FDOQ4683301

Authors: M. H. Khalifeh, Bruce E. Sagan, Emad Zahedi 

Publication date: 20 September 2018

Abstract: If $G$ is a graph then a subgraph $H$ is $isometric$ if, for every pair of vertices $u,v$ of $H$, we have $d_H(u,v)=d_G(u,v)$ where $d$ is the distance function. We say a graph $G$ is $distancepreserving(dp)$ if it has an isometric subgraph of every possible order up to the order of $G$. We give a necessary and sufficient condition for the lexicographic product of two graphs to be a dp graph. A graph $G$ is $sequentiallydistancepreserving(sdp)$ if the vertex set of $G$ can be ordered so that, for all $ige1$, deleting the first $i$ vertices in the sequence results in an isometric graph. We show that the Cartesian product of two graphs is sdp if and only if each of them is sdp. In closing, we state a conjecture concerning the Cartesian products of dp graphs.

Full work available at URL: https://arxiv.org/abs/1507.04800

Recommendations

• Modular decomposition of graphs and the distance preserving property
• On constructing regular distance-preserving graphs
• On a conjecture about the existence of isometric subgraphs
• scientific article; zbMATH DE number 1161357
• On distance-preserving elimination orderings in graphs: complexity and algorithms

zbMATH Keywords

Cartesian productlexicographic productisometric subgraphdistance preserving graphsequentially distance preserving graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Cited In (7)

• Addressing graph products and distance-regular graphs
• On a conjecture about the existence of isometric subgraphs
• Distance-preserving subgraphs of Johnson graphs
• On constructing regular distance-preserving graphs
• On distance-preserving elimination orderings in graphs: complexity and algorithms
• Preliminary results on distance-preserving graphs
• Modular decomposition of graphs and the distance preserving property

This page was built for publication: Distance preserving graphs and graph products.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4683301)