(1,N)-arithmetic graphs

摘要

A (p, q)-graph G is said to be (1,N)-arithmetic if there is a function φ from the vertex set V(G) to {0,1,N,(N + 1),2N,(2N + 1),..., N(q - 1),N(q - 1) + 1} so that the values obtained as the sums of the labeling assigned to their end vertices, can be arranged in the arithmetic progression {1,N + 1,2N + 1,...,N(q - 1) + 1}. In this paper, we prove that Stars, Paths, complete bipartite graph K_(m,n), highly irregular graph H_i(m,m) and Cycle C_(4k) are (1,N)-arithmetic,C_(4k+2) is not (1,N)-arithmetic. We also prove that no graph G containing an odd cycle is (1,N)-arithmetic for every positive integer N.