An α-labeling of a bipartite graph Γ of size e is an injective function f : V (Γ) → {0, 1, 2, . . . , e} such that {|ƒ(x) − ƒ(y)| : [x, y] ∈ E(Γ)} = {1, 2, . . . , e} and with the property that its maximum value on one of the two bipartite sets does not reach its minimum on the other one. We prove that the generalized Petersen graph PSn,3 admits an α-labeling for any integer n ≥ 1 confirming that the conjecture posed by Vietri in [10] is true. In such a way we obtain an infinite class of decompositions of complete graphs into copies of PSn,3.
@article{bwmeta1.element.doi-10_7151_dmgt_1776,
author = {Anna Benini and Anita Pasotti},
title = {$\alpha$-Labelings of a Class of Generalized Petersen Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {43-53},
zbl = {1307.05193},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1776}
}
Anna Benini; Anita Pasotti. α-Labelings of a Class of Generalized Petersen Graphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 43-53. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1776/
[1] P. Adams and D.E. Bryant, The spectrum problem for the Petersen graph, J. Graph Theory 22 (1996) 175-180. doi:10.1002/(SICI)1097-0118(199606)22:2h175::AID-JGT8i3.0.CO;2-K[Crossref] | Zbl 0852.05072
[2] A. Bonisoli, M. Buratti and G. Rinaldi, Sharply transitive decompositions of complete graphs into generalized Petersen graphs, Innov. Incidence Geom. 6/7 (2007/08) 95-109. | Zbl 1213.05204
[3] D. Bryant and S. El-Zanati, Graph decompositions, in: CRC Handbook of Combi- natorial Designs (C.J. Colbourn and J.H. Dinitz Eds.), CRC Press, Boca Raton, FL (2006) 477-486.
[4] R. Frucht and J.A. Gallian, Labeling prisms, Ars Combin. 26 (1988) 69-82. | Zbl 0678.05053
[5] J.A. Gallian, A dynamic survey of graph labelings, Electron. J. Combin. 16 (2013) DS6.
[6] T.A. Redl, Graceful graphs and graceful labelings: Two mathematical programming formulations and some other new results, Congr. Numer. 164 (2003) 17-31. | Zbl 1048.05073
[7] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967) 349-355.
[8] A. Vietri, A new infinite family of graceful generalised Petersen graphs, via “graceful collages” again, Australas. J. Combin. 41 (2008) 273-282. | Zbl 1156.05053
[9] A. Vietri, Erratum: A little emendation to the graceful labelling of the generalised Petersen graph P8t,3 when t = 5: “Graceful labellings for an infinite class of general- ized Petersen graphs” [Ars. Combin. 81 (2006), 247-255; MR2267816], Ars Combin. 83 (2007) 381. | Zbl 1189.05156
[10] A. Vietri, Graceful labellings for an infinite class of generalised Petersen graphs, Ars Combin. 81 (2006) 247-255. | Zbl 1189.05156