Characterizations of Additively Graceful Signed Paths and Cycles

Articles in Press

Document Type : Original paper

Authors

School of Physical and Applied Sciences, Goa University, Taleigao Plateau, Goa 403206, India

Abstract

A $(p,m,n)$ signed graph $S$, is a signed graph of order $p$ with $m$ positive edges and $n$ negative edges. In this paper, we first prove a few basic results on vertex labelings of paths. We use these results and a sequence of lemmas to obtain a characterization of additively graceful signed paths. We prove that, apart from exactly 4 exceptions, additively graceful signed paths are characterized by the signed paths containing at most one negative section with $n \leq 2$. We also establish a characterization of additively graceful signed cycles. We prove that a $(p,m,n)$ signed cycle $S$ is additively graceful if and only if one among the following 4 conditions are satisfied, (a) $n=0$ and $ m\equiv 0$ or $3 \pmod 4$,  (b) $n=1$ and $ m\equiv 1$ or $2 \pmod 4$,  (c) $n=2$, $ m\equiv 1$ or $2 \pmod 4$ and $S$ contains a single negative section,  (d) $S$ is the all negative signed cycle on $C_3$.
 

Keywords

Main Subjects

References

1] R. Alexander, On certain valuations of the vertices of a graph, theory of graphs (internat. symposium, rome, july 1966), Gordon and Breach, NY and Dunod Paris, 1967.
[2] R. Cattell, Graceful labellings of paths, Discrete Math. 307 (2007), no. 24, 3161–3176. https://doi.org/10.1016/j.disc.2007.03.046
[3] Gary Chartrand, Linda Lesniak, and Ping Zhang, Graphs & Digraphs, vol. 39, CRC press, 2010.
[4] S.W. Golomb, How to number a graph, Graph theory and computing (R.C. Read, ed.), Elsevier, 1972, pp. 23–37. https://doi.org/10.1016/B978-1-4832-3187-7.50008-8
[5] S.M. Hegde, Additively graceful graphs, Nat. Acad. Sci. Lett 12 (1989), 387–390.
[6] J. Pereira, T. Singh, and S. Arumugam, Additively graceful signed graphs, AKCE Int. J. Graphs Comb. 20 (2023), no. 3, 300–307.  https://doi.org/10.1080/09728600.2023.2243619
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 01 May 2025

Files

Share

How to cite

Statistics