(Di)graph Decompositions and Magic Type Labelings: A Dual Relation
- PDF / 508,596 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 192 Views
(Di)graph Decompositions and Magic Type Labelings: A Dual Relation Susana-Clara López1
· Francesc-Antoni Muntaner-Batle2 · Mohan Prabu3
Received: 8 June 2020 / Revised: 31 August 2020 / Accepted: 9 October 2020 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract A graph G is called edge-magic if there is a bijective function f from the set of vertices and edges to the set {1, 2, . . . , |V (G)|+|E(G)|} such that the sum f (x)+ f (x y)+ f (y) for any x y in E(G) is constant. Such a function is called an edge-magic labeling of G, and the constant is called the valence of f . An edge-magic labeling with the extra property that f (V (G)) = {1, 2, . . . , |V (G)|} is called super edge-magic. In this paper, we establish a relationship between the valences of (super) edge-magic labelings of certain types of bipartite graphs and the existence of a particular type of decompositions of such graphs. Keywords Edge-magic · Super edge-magic · Magic sum · ⊗h -product · Decompositions Mathematics Subject Classification 05C78 · 05C76
Communicated by Sandi Klavžar.
B
Susana-Clara López [email protected] Francesc-Antoni Muntaner-Batle [email protected] Mohan Prabu [email protected]
1
Departament de Matemàtica, Universitat de Lleida, Av/Pla de la Massa, 8, 08700 Igualada, Barcelona, Spain
2
Graph Theory and Applications Research Group School of Electrical Engineering and Computer Science Faculty of Engineering and Built Environment, The University of Newcastle, NSW 2308, Australia
3
British University Vietnam, Hanoi, Vietnam
123
S.-C. López et al.
1 Introduction For the terminology and notation not introduced in this paper, we refer the reader to either one of the following sources [2,3,8,13,21]. By a ( p, q)-graph, we mean a graph of order p and size q. Let m ≤ n be integers, to denote the set {m, m +1, . . . , n} we use [m, n]. The Kronecker product of two (di)graphs G 1 = (V1 , E 1 ) and G 2 = (V2 , E 2 ) is the (di)graph G 1 ⊗ G 2 with vertex set V1 × V2 and with an (arc) edge ((a, b), (c, d)) whenever (a, c) ∈ E 1 and (b, d) ∈ E 2 . The crown product of two graphs G 1 and G 2 is the graph G = G 1 G 2 obtained by placing a copy of G 1 and |V (G 1 )| copies of G 2 and then joining each vertex of G 1 with all vertices in one copy of G 2 in such a way that all vertices in the same copy of G 2 are joined with exactly one vertex of G 1 . Kotzig and Rosa introduced in [12] the concepts of edge-magic graphs and edge-magic labelings as follows: Let G be a ( p, q)-graph. Then, G is called edge-magic if there is a bijective function f : V (G) ∪ E(G) → [1, p + q] such that the sum f (x) + f (x y) + f (y) = k for any x y ∈ E(G). Such a function is called an edge-magic labeling of G, and k is called the valence [12] or the magic sum [21] of the labeling f . We write val( f ) to denote the valence of f . Inspirated by the notion of edge-magic labelings, Enomoto et al. introduced in [4] the concepts of super edge-magic graphs and super edge-magic labelings as follows: Let f :
Data Loading...
