No Access

Characterizing 2-distance graphs

Department of Physical Sciences and Mathematics, College of Arts and Sciences, University of the Philippines Manila, Manila, The Philippines

E-mail Address: ramuelching@gmail.com

Search for more papers by this author

and

I. J. L. Garces

http://orcid.org/0000-0002-3607-1439

Department of Mathematics, Ateneo de Manila University, Quezon City, The Philippines

E-mail Address: ijlgarces@ateneo.edu

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S1793557119500062Cited by:3 (Source: Crossref)

Abstract

Let $X$ $X$ be a finite simple graph. The $2$ $2$ -distance graph $D_{2} (X)$ $D_{2} (X)$ of $X$ $X$ is the graph with the same vertex set as $X$ $X$ and two vertices are adjacent if and only if their distance in $X$ $X$ is exactly $2$ $2$ . A graph $G$ $G$ is a $2$ $2$ -distance graph if there exists a graph $X$ $X$ such that $D_{2} (X) ≅ G$ $D_{2} (X) ≅ G$ . In this paper, we give three characterizations of $2$ $2$ -distance graphs, and find all graphs $X$ $X$ such that $D_{2} (X) ≅ k P_{2}$ $D_{2} (X) ≅ k P_{2}$ or $K_{m} \cup K_{n}$ $K_{m} \cup K_{n}$ , where $k \geq 2$ $k \geq 2$ is an integer, $P_{2}$ $P_{2}$ is the path of order $2$ $2$ , and $K_{m}$ $K_{m}$ is the complete graph of order $m \geq 1$ $m \geq 1$ .

Communicated by L. A. Bokut

Keywords:

AMSC: 05C12

References

1. J. Akiyama and F. Harary, A graph and its complement with specified properties I: connectivity, Internat. J. Math. Math. Sci. 2(2) (1979) 223–228. Crossref, Google Scholar
2. A. Azimi and M. Farrokhi, D. G. , Simple graphs whose 2-distance graphs are paths or cycles, Matematiche (Catania) 69(2) (2014) 183–191. Google Scholar
3. A. Azimi and M. Farrokhi, D. G. , Self 2-distance graphs, Canad. Math. Bull. 60(1) (2017) 26–42. Crossref, Web of Science, Google Scholar
4. G. S. Bloom, J. W. Kennedy and L. V. Quintas, A characterization of graphs of diameter two, Amer. Math. Monthly 95(1) (1988) 37–38. Crossref, Web of Science, Google Scholar
5. J. W. Boland, T. W. Haynes and L. M. Lawson, Domination from a distance, Congr. Numer. 103 (1994) 89–96. Google Scholar
6. J. A. Bondy and U. S. R. Murty, Graph Theory (Springer, 2008). Crossref, Google Scholar
7. F. Harary, C. Hoede and D. Kadlecek, Graph-valued functions related to step graphs, J. Comb. Inf. Syst. Sci. 7 (1982) 231–246. Google Scholar
8. F. Harary and R. W. Robinson, The diameter of a graph and its complement, Amer. Math. Monthly 92(3) (1985) 211–212. Crossref, Web of Science, Google Scholar
9. J. C. T. Leonor, Periodicity and convergence of graphs under the 2-distance operator, Master’s Thesis (unpublished), Pamantasan ng Lungsod ng Marikina, 2017. Google Scholar
10. E. Prisner, Graph Dynamics (Longman House, 1995). Google Scholar
11. G. Ringel, Selbstkomplementäre Graphen, Arch. Math. 14 (1963) 354–358. Crossref, Google Scholar
12. H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962) 270–288. Crossref, Google Scholar
13. B. Zelinka, A note on periodicity of the 2-distance operator, Discuss. Math. Graph Theory 20 (2000) 267–269. Crossref, Google Scholar