α-Labelings of a Class of Generalized Petersen Graphs

• Autorzy: Anna Benini , Anita Pasotti
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

generalized Petersen graph; -labeling; graph decomposit

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 1
• Strony: 43-53

Daty

wydano

2015-02-01

otrzymano

2013-02-21

poprawiono

2014-01-13

zaakceptowano

2014-01-29

online

2015-02-06

Twórcy

autor

Anna Benini

• DICATAM - Sezione di Matematica Università degli Studi di Brescia Via Valotti 9, I-25133 Brescia, Italy

autor

Anita Pasotti

• DICATAM - Sezione di Matematica Università degli Studi di Brescia Via Valotti 9, I-25133 Brescia, Italy

Bibliografia

• [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]
• [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 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.
• [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 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.
• [10] A. Vietri, Graceful labellings for an infinite class of generalised Petersen graphs, Ars Combin. 81 (2006) 247-255.

Identyfikatory

DOI

10.7151/dmgt.1776