Graceful signed graphs: II. The case of signed cycles with connected negative sections

摘要

In our earlier paper [9], generalizing the well known notion of graceful graphs, a (p, m, n)-signed graph S of order p, with m positive edges and n negative edges, is called graceful if there exists an injective function f that assigns to its p vertices integers 0, 1,...,q = m + n such that when to each edge uv of S one assigns the absolute difference |f(u)-f(v)| the set of integers received by the positive edges of S is {1,2,...,m} and the set of integers received by the negative edges of S is {1,2,...,n}. Considering the conjecture therein that all signed cycles Z k , of admissible length k ≥ 3 and signed structures, are graceful, we establish in this paper its truth for all possible signed cycles of lengths 0, 2 or 3 (mod 4) in which the set of negative edges forms a connected subsigraph.