scientific article; zbMATH DE number 19170
[For the entire collection see Zbl 0734.00014.] A snake \(P_ n\) is a tree with \(n\) edges and exactly two endvertices. An \(\alpha\)-valuation of a graph \(G\) is a graceful numbering \(f\) on \(G\) for which there is a number \(c\), \(0\leq c\leq| E(G)|\), such that for any edge \(uv\) of \(G\) we have \(\min[f(u),f(v)]\leq c\leq\max[f(u),f(v)]\). If \(G\) has an \(\alpha\)-valuation \(f\), we set \(L(G)=\{v\in V(G);f(v)\leq c\}\), and \(U(G)=V(G)-L(G)\). An \(\alpha\)-valuation \(f\) of \(P_ n\) is called separable if there is a non-pendant edge \(e\) of \(P_ n\) such that for the two snakes \(Q_ 1\), \(Q_ 2\) whose union is \(P_ n-e\) it holds that each of the four sets \(f(V(Q_ i)\cap L(P_ n))\), \(f(V(Q_ i)\cap U(P_ n))\), \(i=1,2\), is either an integer interval or a one-element set. As the main result, it is shown that \(P_ n\) has an \(\alpha\)-valuation which is not separable if and only if either \(n\in\{1,2,6\}\) or \(n\geq 8\).
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976598)
