Additively graceful signed graphs on complete graphs and some open problems resolved
Ars Combinatoria · 09.05.2026 · 167 · 29-43
DOI: 10.61091/ars167-02 ↗Kurz gefasst
Fachartikel in der Zeitschrift Ars Combinatoria, online erschienen am 09.05.2026. Verfasst von Brian D’Souza und 1 weiteren Autor:innen.
Abstract (Originalsprache)
We prove the following necessary conditions for signed graphs on complete graphs to admit additive graceful labelings, thus considerably narrowing down the search for such labelings. If a signed graph on a complete graph \(K_p, ~p\not = 4\), with \(n\) negative and \(m\) positive edges, admits an additively graceful labeling, then (1) \(p\), \(p-2\) or \(p-4\) must be a perfect square, (2) If \(p\) is a perfect square then, both \(m\) and \(n\) are even, (3) If \(p-4\) is a perfect square then, both \(m\) and \(n\) are odd, (4) If \(p-2\) is a perfect square then, \(m\) and \(n\) have opposite parity and (5) The number of odd and even labeled vertices in \(S\) are \(\frac{p+\sqrt{p-i}}{2}\) and \(\frac{p-\sqrt{p-i}}{2}\) according as \(p-i\) is a perfect square, \(i=0,2\) or \(4\). We also provide an example to show that, if a signed graph \(S\) with no negative edges is additively graceful then, \(S\) as a graph need not be graceful. Interestingly, this example also settles 3 more open problems concerning gracefulness and edge consecutive gracefulness (ecg), thereby demonstrating that ecg or \(m\)-gracefulness is not a reliable measure of gracefulness.
Zitieren
APA
D’Souza, B., & Pereira, J. (2026). Additively graceful signed graphs on complete graphs and some open problems resolved. Ars Combinatoria, 167, 29-43. https://doi.org/10.61091/ars167-02
Vancouver
D’Souza B, Pereira J. Additively graceful signed graphs on complete graphs and some open problems resolved. Ars Combinatoria. 2026;167:29-43. doi:10.61091/ars167-02
BibTeX
@article{DSouza2026,
author = {D’Souza, Brian and Pereira, Jessica},
title = {Additively graceful signed graphs on complete graphs and some open problems resolved},
journal = {Ars Combinatoria},
year = {2026},
volume = {167},
pages = {29--43},
doi = {10.61091/ars167-02}
}
EUVIMED