Distance preserving graphs and graph products.

MaRDI QIDQ4683301zbMATH OpenFDO

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

Publication date 20 September 2018

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

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)

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.

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

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)