Geodesic
α-Labelings of a Class of Generalized Petersen Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 1, pp. 43-53.

Voir la notice de l'article provenant de la source Library of Science

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 P_Sn,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 P_Sn,3.
Keywords: generalized Petersen graph, α-labeling, graph decomposition 
@article{DMGT_2015_35_1_a3,
     author = {Benini, Anna and Pasotti, Anita},
     title = {\ensuremath{\alpha}-Labelings of a {Class} of {Generalized} {Petersen} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {43--53},
     publisher = {mathdoc},
     volume = {35},
     number = {1},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a3/}
}
TY  - JOUR
AU  - Benini, Anna
AU  - Pasotti, Anita
TI  - α-Labelings of a Class of Generalized Petersen Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 43
EP  - 53
VL  - 35
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a3/
LA  - en
ID  - DMGT_2015_35_1_a3
ER  - 
%0 Journal Article
%A Benini, Anna
%A Pasotti, Anita
%T α-Labelings of a Class of Generalized Petersen Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 43-53
%V 35
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a3/
%G en
%F DMGT_2015_35_1_a3
Benini, Anna; Pasotti, Anita. α-Labelings of a Class of Generalized Petersen Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 1, pp. 43-53. http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a3/

[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

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

[3] D. Bryant and S. El-Zanati, Graph decompositions, in: CRC Handbook of Combinatorial 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.

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

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

[9] A. Vietri, Erratum: A little emendation to the graceful labelling of the generalised Petersen graph $P_{8t,3}$ when t = 5: “Graceful labellings for an infinite class of generalized Petersen graphs” [Ars. Combin. 81 (2006), 247-255; MR2267816], Ars Combin. 83 (2007) 381.

[10] A. Vietri, Graceful labellings for an infinite class of generalised Petersen graphs, Ars Combin. 81 (2006) 247-255.