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≤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≡0 or 3(mod4),  (b) n=1 and m≡1 or 2(mod4),  (c) n=2, m≡1 or 2(mod4) and S contains a single negative section,  (d) S is the all negative signed cycle on C3.
 

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