Connectivity of 2-distance graphs

Document Type : Research Paper

Authors

Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran

Abstract

For a simple graph $G$, the $2$-distance graph, $D_2(G)$, is a graph with the vertex set $V(G)$ and two vertices are adjacent if their distance is $2$ in the graph $G$. In this paper, we characterize all graphs with connected $2$-distance graphs. For graphs with diameter 2, we prove that $D_2(G)$ is connected if and only if $G$ has no spanning complete bipartite subgraphs.  For graphs whose diameter is greater than $2$, we define a maximal fine set, and by contracting $G$ with respect to these subsets, we obtain a new graph $\widehat{G}$  such that $D_2(G)$ is connected if and only if $D_2(\widehat{G})$ is connected. In particular, $D_2(G)$ is disconnected if and only if $\widehat{G}$ is bipartite.

Keywords

Main Subjects

References

[1] Azimi A., & Farrokhi D.G. M. (2017). Self 2-distance graphs. Canadian Mathematical Bulletin, 60(1), 26{42. https://doi.org/10.4153/CMB-2016-071-6.
[2] Azimi A., & Farrokhi D.G. M. (2014). Simple graphs whose 2-distance graphs are paths or cycles. Le Matematiche (Catania), 69(2), 183{191. https://doi.org/10.4418/2014.69.2.16.
[3] Boland J. W., Haynes T. W., & Lawson L. M. (1994). Domination from a distance. Congressus Numerantium, 103, 89{96.
[4] Ching R. P. (2019). Characterizing 2-distance graphs. Asian-European Journal of Mathematics, 12(1), 1950006. https://doi.org/10.1142/S1793557119500062.
[5] Gaar E., & Krenn D. (2023). A characterization of graphs with regular distance-2 graphs. Discrete Applied Mathematics, 324. https://doi.org/10.1016/j.dam.2022.09.020.
[6] Harary F., Hoede C., & Kadlecek D. (1982). Graph-valued functions related to step graphs. Journal of Combinatorics, Information and System Sciences, 7, 231{246.
[7] Khormali O. (2017). On the connectivity of k-distance graphs. Electronic Journal of Graph Theory and Applications, 5(1), 83-93. http://dx.doi.org/10.5614/ejgta.2017.5.1.9.
[8] Leonor J. C. T. (2017). Periodicity and convergence of graphs under the 2-distance operator. Master's Thesis (unpublished), Pamantasan ng Lungsod ng Marikina, (PLMar,Marikina, Philippines).
[9] Prisner E. (1995). Graph Dynamics. Longman House.
[10] Rajkumar R., & Celine Prabha S. (2019). Solutions of some 2-distance graph equations. AIP Conference Proceedings, 2112, 020109. https://doi.org/10.1063/1.5112294.
[11] Zelinka B. (2000). A note on periodicity of the 2-distance operator. Discussiones Mathematicae Graph Theory, 20, 267{269. https://doi.org/10.7151/dmgt.1125. 

Files

History

  • Receive Date: 23 January 2025
  • Revise Date: 15 November 2025
  • Accept Date: 20 December 2025

Share

How to cite

Statistics