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.
维普
万方数据