# α-Labelings of a Class of Generalized Petersen Graphs

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 1, page 43-53
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAnna Benini, and Anita Pasotti. "α-Labelings of a Class of Generalized Petersen Graphs." Discussiones Mathematicae Graph Theory 35.1 (2015): 43-53. <http://eudml.org/doc/271220>.

@article{AnnaBenini2015,

abstract = {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.},

author = {Anna Benini, Anita Pasotti},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {generalized Petersen graph; -labeling; graph decomposit; -labeling},

language = {eng},

number = {1},

pages = {43-53},

title = {α-Labelings of a Class of Generalized Petersen Graphs},

url = {http://eudml.org/doc/271220},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Anna Benini

AU - Anita Pasotti

TI - α-Labelings of a Class of Generalized Petersen Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 1

SP - 43

EP - 53

AB - 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.

LA - eng

KW - generalized Petersen graph; -labeling; graph decomposit; -labeling

UR - http://eudml.org/doc/271220

ER -

## References

top- [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] Zbl0852.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. Zbl1213.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. Zbl0678.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. Zbl1048.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. Zbl1156.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. Zbl1189.05156
- [10] A. Vietri, Graceful labellings for an infinite class of generalised Petersen graphs, Ars Combin. 81 (2006) 247-255. Zbl1189.05156

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.