×

Integral sum graphs from a class of trees. (English) Zbl 1092.05059

Summary: A graph \(G=(V,E)\) is said to be an integral sum graph (respectively, sum graph) if there is a labeling \(f\) of its vertices with distinct integers (respectively, positive integers), so that for any two vertices \(u\) and \(v\), \(uv\) is an edge of \(G\) if and only if \(f(u)+f(v)=f(w)\) for some other vertex \(w\). For a given graph \(G\), the integral sum number \(\zeta = \zeta (G)\) (respectively, sum number \(\sigma = \sigma (G)\)) is defined to be the smallest number of isolated vertices which when added to \(G\) result in an integral sum graph (respectively, sum graph). In a graph \(G\), a vertex \(v \in V(G)\) is said to be a hanging vertex if the degree of it \(d(v)=1\). A path \(P \subseteq G\), \(P=x_0x_1x_2 \cdots x_t\), is said to be a hanging path if its two end vertices are respectively a hanging vertex \(x_0\) and a vertex \(x_t\) whose degree \(d(x_t) \neq 2\) where \(d(x_j)=2\;(j=1,2,\dots , t-1)\) for every other vertex of \(P\). A hanging path \(P\) is said to be a tail of \(G\), denoted by \(t(G)\), if its length \(| t(G)| \) is a maximum among all hanging paths of \(G\). In this paper, we prove \(\zeta (T_3) =0\), where \(T_3\) is any tree with \(| t(T_3) | \geq 3\).

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite