2015/10/04 by Ramuel P. Ching, Ching, Ramuel P., I. J. L. Garces +1
Mathematics · #05C12 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C12
paper · pdf · doi:10.48550/arxiv.1510.00924
arxiv created 2015/10/04 · arxiv updated 2015/10/06
Let X be a finite, simple graph with vertex set V(X). The 2-distance graph T2(X) of X is the graph with the same vertex set as X and two vertices are adjacent if and only if their distance in X is exactly 2. A graph G is a 2-distance graph if there exists a graph X such that T2(X)=G. In this paper, we give three characterizations of 2-distance graphs, and find all graphs X such that T2(X)=kP2 or Km ∪ Kn, where k ≥ 2 is an integer, P2 is the path of order 2, and Km is the complete graph of order m ≥ 1.