Abstract：A graph G is called an exact-3-relation graph， if there is an edge-labeled tree T such that the set of leaves of the tree T is equal to the set of vertices of the graph G， and xy is an edge of the graph G if and only if the sum of the lables of the edges on the unique path from x to y is 3 in the tree T. In this paper， the following question is discussed： what kind of graph is an exact-3-relation graph. Bipartite graph is the necessary condition that a graph is an exact-3-relation graph is proved， that is， as long as a graph G contains odd cycles， then the graph G is not an exact-3-relation graph. Furthermore， we completely describe the necessary and sufficient conditions that the cycle graphs are the exact-3-relation graphs， that is， a cycle graph is an exact-3-relation graph if and only if the cycle graph is an even cycle， and we give the edge-labeled trees corresponding to the even cycles with respect to exact-3-relation. Finally， the condition that the small graphs are the exact-3-relation graphs is discussed. It is proved that a graph of order at most 7 is an exact-3-relation graph if and only if the graph is bipartite graph.
2024, Vol. 58 
