Diameter of 2-distance graphs

2024/03/12 by Jafari, S. H., Musawi, S. R.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2403.07646

Abstract

For a simple graph G, the 2-distance graph, D₂(G), is a graph with the vertex set V(G) and two vertices are adjacent if and only if their distance is 2 in the graph G. In this paper, for graphs G with diameter 2, we show that diam(D₂(G)) can be any integer t\geqslant2. For graphs G with diam(G)\geqslant3, we prove that (1)/(2)diam(G)\leqslant diam(D₂(G)) and this inequality is sharp. Also, for diam(G)=3, we prove that diam(D₂(G))\leqslant5 and this inequality is sharp.

Related

• Diameter Constraints in 2-distance Graphs
• Connectivity of 2-distance graphs
• A new approach for computing the distance and the diameter in circulant graphs
• Universal diameter bounds for random graphs with given degrees
• Characterizing 2-Distance Graphs and Solving the Equations T₂(X)=kP₂ or K_m ∪ K_n