Labeling the vertex amalgamation of graphs
Ramon M. Figueroa-Centeno ; Rikio Ichishima ; Francesc A. Muntaner-Batle
Discussiones Mathematicae Graph Theory, Tome 23 (2003), p. 129-139 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

A graph G of size q is graceful if there exists an injective function f:V(G)→ 0,1,...,q such that each edge uv of G is labeled |f(u)-f(v)| and the resulting edge labels are distinct. Also, a (p,q) graph G with q ≥ p is harmonious if there exists an injective function f:V(G)→Zq such that each edge uv of G is labeled f(u) + f(v) mod q and the resulting edge labels are distinct, whereas G is felicitous if there exists an injective function f:V(G)→Zq+1 such that each edge uv of G is labeled f(u) + f(v) mod q and the resulting edge labels are distinct. In this paper, we present several results involving the vertex amalgamation of graceful, felicitous and harmonious graphs. Further, we partially solve an open problem of Lee et al., that is, for which m and n the vertex amalgamation of n copies of the cycle Cₘ at a fixed vertex v ∈ V(Cₘ), Amal(Cₘ,v,n), is felicitous? Moreover, we provide some progress towards solving the conjecture of Koh et al., which states that the graph Amal(Cₘ,v,n) is graceful if and only if mn ≡ 0 or 3 mod 4. Finally, we propose two conjectures.

Publié le : 2003-01-01
EUDML-ID : urn:eudml:doc:270335 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1190,
     author = {Ramon M. Figueroa-Centeno and Rikio Ichishima and Francesc A. Muntaner-Batle},
     title = {Labeling the vertex amalgamation of graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {23},
     year = {2003},
     pages = {129-139},
     zbl = {1054.05087},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1190}
}

Ramon M. Figueroa-Centeno; Rikio Ichishima; Francesc A. Muntaner-Batle. Labeling the vertex amalgamation of graphs. Discussiones Mathematicae Graph Theory, Tome 23 (2003) pp. 129-139. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1190/

[000] [1] G. Chartrand and L. Leśniak, Graphs and Digraphs (Wadsworth &Brooks/Cole Advanced Books and Software, Monterey, Calif. 1986). | Zbl 0666.05001

[001] [2] J. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (2002) #DS6. | Zbl 0953.05067

[002] [3] R.L. Graham and N.J.A. Sloane, On additive bases and harmonious graphs, SIAM J. Alg. Discrete Math. 1 (1980) 382-404, doi: 10.1137/0601045. | Zbl 0499.05049

[003] [4] K.M. Koh, D.G. Rogers, P.Y. Lee and C.W. Toh, On graceful graphs V: unions of graphs with one vertex in common, Nanta Math. 12 (1979) 133-136. | Zbl 0428.05048

[004] [5] S.M. Lee, E. Schmeichel and S.C. Shee, On felicitous graphs, Discrete Math. 93 (1991) 201-209, doi: 10.1016/0012-365X(91)90256-2. | Zbl 0741.05059

[005] [6] 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) 87-95.

[006] [7] S.C. Shee, On harmonious and related graphs, Ars Combin. 23 (1987) (A) 237-247. | Zbl 0616.05055

[007] [8] S.C. Shee, Some results on λ-valuation of graphs involving complete bipartite graphs, Discrete Math. 28 (1991) 1-14.