The consecutively super edge-magic deficiency of graphs and related concepts
Abstract
A bipartite graph G with partite sets X and Y is called consecutively super edge-magic if there exists a bijective function f : V(G) ⋃ E(G) → {1,2,...,|V(G)| + |E(G)|} with the property that f(X) = {1,2,...,|X|}, f(Y) = {|X|+1, |X|+2,...,|V(G)|} and f(u)+f(v) +f(uv) is constant for each uv ∈ E(G). The question studied in this paper is for which bipartite graphs it is possible to add a finite number of isolated vertices so that the resulting graph is consecutively super edge-magic. If it is possible for a bipartite graph G, then we say that the minimum such number of isolated vertices is the consecutively super edge-magic deficiency of G; otherwise, we define it to be +∞. This paper also includes a detailed discussion of other concepts that are closely related to the consecutively super edge-magic deficiency.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2020.8.1.6
References
B.D. Acharya and S.M. Hegde, Strongly indexable graphs, Discrete Math., 93 (1991) 123–129.
M.Baca and M.Miller, Super edge-antimagic graphs: a wealth of problems and some solutions, Brown Walker Press, 2007, Boca Raton, FL, USA.
C. Barrientos, The gracefulness of unions of cycles and complete bipartite graphs, J. Combin. Math. Combin. Comput., 52 (2005) 69–78.
R. Cattell, Graceful labellings of paths, Discrete Math., 307 (2007) 3161–3176.
G. Chartrand and L. Lesniak, Graphs & Digraphs, Wadsworth & Brook/Cole Advanced Books and Software, Monterey, Calif. 1986.
H. Enomoto, A. Llado ́, T. Nakamigawa and G. Ringel, Super edge-magic graphs, SUT J. Math., 34 (1998) 105–109.
R.M. Figueroa-Centeno and R. Ichishima, On the sequential number and super edge-magic deficiency of graphs, Ars Combin., 129 (2016) 157–163.
R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On super edge-magic graphs, Ars Combin., 64 (2002) 81–95.
R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On edge-magic labelings of certain disjoint unions of graphs, Australas. J. Combin., 32 (2005) 225–242.
R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, Some new results on the super edge-magic deficiency of graphs, J. Combin. Math. Combin. Comput., 55 (2005) 17– 31.
R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On the super edge-magic deficiency of graphs, Ars Combin., 78 (2006) 33–45.
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.
J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., (2017) #DS6.
S.W. Golomb, How to number a graph, in Graph Theory and Computing, (ed. R.C. Read), Academic Press, New York (1972), 23–37.
S.M. Hegde and S.Shetty, Strongly k-indexable and super edge-magic labelings are equivalent, preprint.
R. Ichishima, S.C. Lopez, F.A. Muntaner-Batle and A. Oshima, On the beta-number of forests with isomorphic components, Discuss. Math. Graph Theory, 38 (2018) 683–701.
R. Ichishima, F.A. Muntaner-Batle and A. Oshima, The measurements of closeness to grace- ful graphs, Australas. J. Combin., 62 (3) (2015) 197–210.
R. Ichishima and A. Oshima,On the super edge-magic deficiency and α-valuations of graphs, J. Indones. Math. Soc., Special Edition (2011) 59–69.
R. Ichishima and A. Oshima, On the super edge-magic deficiency of 2-regular graphs with two components, Ars Combin., 129 (2016) 437–447.
R. Ichishima and A. Oshima, Bounds for the gamma-number of graphs, Util. Math., 109 (2018) 313–325.
A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull., 13 (1970) 451–461.
S.C. Lo ́pez and F.A. Muntaner-Batle, Graceful, Harmonious and Magic Type Labelings: Relations and Techniques, SpringerBriefs in Mathematics, Springer, Cham, 2017.
A.M. Marr and W.D. Wallis, Magic Graphs. Second ed. Birkha ̈user/Springer, New York, 2013.
F.A. Muntaner-Batle, Special super edge-magic labelings of bipartite graphs, J. Combin. Math. Combin. Comput., 39 (2001) 107–120.
A.A.G Ngurah and R. Simanjuntak, On the super edge-magic deficiency of join product and chain graphs, Electron. J. Graph Theory Appl., 7 (1) (2019), 157–167.
A. Oshima, Consecutively super edge-magic tree with diameter 4, Rev. Bull. Calcutta Math. Soc., 15 (2007) 87–90.
A. Oshima, R. Ichishima and F.A. Muntaner-Batle, New parameters for studying graceful properties of graphs, Electron. Notes Discrete Math., 60 (2017) 3–10.
G. Ringel and A. Llado ́, Another tree conjecture, Bull. Inst. Combin. Appl., 18 (1996) 83–85.
A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Sym- posium, Rome, July 1966), Gordon and Breach, N. Y and Dunod Paris (1967), 349–355.
W.D. Wallis, Magic Graphs, Birkha ̈user, Boston, 2001.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.