Geodesic
On the Beta-Number of Forests with Isomorphic Components
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 683-701.

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

The beta-number, β(G), of a graph G is defined to be either the smallest positive integer n for which there exists an injective function f : V (G) → 0, 1, ..., n such that each uv ∈ E (G) is labeled |f (u) − f (v)| and the resulting set of edge labels is c, c+1, ..., c+|E(G)|−1 for some positive integer c or +∞ if there exists no such integer n. If c = 1, then the resulting beta-number is called the strong beta-number of G and is denoted by βs (G). In this paper, we show that if G is a bipartite graph and m is odd, then β (mG) ≤ mβ (G) + m − 1. This leads us to conclude that β (mG) = m|V(G)|−1 if G has the additional property that G is a graceful nontrivial tree. In addition to these, we examine the (strong) beta-number of forests whose components are isomorphic to either paths or stars.
Keywords: beta-number, strong beta-number, graceful labeling, Skolem sequence, hooked Skolem sequence 
@article{DMGT_2018_38_3_a5,
     author = {Ichishima, Rikio and L\'opez, Susana-Clara and Muntaner-Batle, Francesc Antoni and Oshima, Akito},
     title = {On the {Beta-Number} of {Forests} with {Isomorphic} {Components}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {683--701},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a5/}
}
TY  - JOUR
AU  - Ichishima, Rikio
AU  - López, Susana-Clara
AU  - Muntaner-Batle, Francesc Antoni
AU  - Oshima, Akito
TI  - On the Beta-Number of Forests with Isomorphic Components
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 683
EP  - 701
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a5/
LA  - en
ID  - DMGT_2018_38_3_a5
ER  - 
%0 Journal Article
%A Ichishima, Rikio
%A López, Susana-Clara
%A Muntaner-Batle, Francesc Antoni
%A Oshima, Akito
%T On the Beta-Number of Forests with Isomorphic Components
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 683-701
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a5/
%G en
%F DMGT_2018_38_3_a5
Ichishima, Rikio; López, Susana-Clara; Muntaner-Batle, Francesc Antoni; Oshima, Akito. On the Beta-Number of Forests with Isomorphic Components. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 683-701. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a5/

[1] B.D. Acharya and S.M. Hegde, Strongly indexable graphs, Discrete Math. 93 (1991) 123–129. doi:10.1016/0012-365X(91)90248-Z

[2] R. Cattell, Graceful labellings of paths, Discrete Math. 307 (2007) 3161–3176. doi:10.1016/j.disc.2007.03.046

[3] G. Chartrand and L. Lesniak, Graphs & Digraphs (Wadsworth & Brook/Cole Advanced Books and Software, Monterey, Calif., 1986).

[4] A.R. Eckler, Construction of missile guidance codes resistant to random interference, Bell Syst. Tech. J. 39 (1960) 937–994. doi:10.1002/j.1538-7305.1960.tb03950.x

[5] H. Enomoto, A. Lladó, T. Nakamigawa and G. Ringel, Super edge-magic graphs, SUT J. Math. 34 (1998) 105–109.

[6] R.M. Figueroa-Centeno, R. Ichishima, F.A. Muntaner-Batle and M. Rius-Font, Labeling generating matrices, J. Combin. Math. Combin. Comput. 67 (2008) 189–216.

[7] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 19 (2016) #DS6.

[8] S.W. Golomb, How to number a graph, in: Graph Theory and Computing, R.C. Read, Ed. (Academic Press, New York, 1972) 23–37.

[9] R. Ichishima, F.A. Muntaner-Batle and A. Oshima, The measurements of closeness to graceful graphs, Australas. J. Combin. 63 (2015) 197–210.

[10] E.S. O’Keefe, Verification of a conjecture of Th. Skolem, Math. Scand. 9 (1961) 80–82. doi:10.7146/math.scand.a-10624

[11] S.C. López and F.A. Muntaner-Batle, Langford sequences and a product of digraphs, European J. Combin. 53 (2016) 86–95. doi:10.1016/j.ejc.2015.11.004

[12] S.C. López, F.A. Muntaner-Batle and M. Rius-Font, Labeling constructions using digraphs products, Discrete Appl. Math. 161 (2013) 3005–3016. doi:10.1016/j.dam.2013.06.006

[13] A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs (Internat. Symposium, Rome, July 1966), (Gordon and Breach, N.Y. and Dunod, Paris, 1967) 349–355.

[14] A. Rosa, Labeling snakes, Ars Combin. 3 (1977) 67–73.

[15] A. Rosa and J. Širáň, Bipartite labelings of trees and the gracesize, J. Graph Theory 19 (1995) 201–215. doi:10.1002/jgt.3190190207

[16] N. Shalaby, Skolem sequences, in: Handbook of Combinatorial Designs, Second Edition, C.J. Colbourn and J.H. Dinitz (Eds.), Discrete Mathematics and its Applications (Chapman & Hall/CRC, Boca Raton, FL, 2007) 612–617.

[17] T. Skolem, On certain distribution of integers into pairs with given differences, Math. Scand. 5 (1957) 57–68. doi:10.7146/math.scand.a-10490