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

Acharya, Mukti ; Singh, Tarkeshwar

Czechoslovak Mathematical Journal, Tome 55 (2005) no. 1, pp. 25-40.

Résumé

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,\dots ,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 $\lbrace 1,2,\dots ,m\rbrace $ and the set of integers received by the negative edges of $S$ is $\lbrace 1,2,\dots ,n\rbrace $. Considering the conjecture therein that all signed cycles $Z_k$, of admissible length $ k \ge 3$ and signed structures, are graceful, we establish in this paper its truth for all possible signed cycles of lengths $ 0,2$ or $3\hspace{4.44443pt}(\@mod \; 4)$ in which the set of negative edges forms a connected subsigraph.

Détail

Classification : 05C22, 05C78
Keywords: graceful signed graphs; signed cycles