Antimagicness of Lexicographic Product Graph G [ P n ]
- PDF / 240,525 Bytes
- 17 Pages / 612 x 792 pts (letter) Page_size
- 93 Downloads / 176 Views
Acta Mathemacae Applicatae Sinica, English Series The Editorial Office of AMAS & Springer-Verlag GmbH Germany 2020
Antimagicness of Lexicographic Product Graph G[Pn ] Ying-yu LU1,2 , Guang-hua DONG1,† , Ning WANG3 1 School
of Mathematical Sciences, Tiangong University, Tianjin 300387, China († E-mail: [email protected])
2 Lushan
College of Guangxi University of Science and Technology, Liuzhou 545000, China of Information Science and Technology, Tianjin University of Finance and Economics, Tianjin
3 Department
300222, China
Abstract
Hartsfield and Ringel conjectured that every connected graph other than K2 is antimagic. Since
then, many classes of graphs have been proved to be antimagic. But few is known about the antimagicness of lexicographic product graphs. In this paper, via the construction of a directed Eulerian circuit, the Siamese method, and some modification on graph labeling, the antimagicness of lexicographic product graph G[Pn ] is obtained. Keywords
antimagic; labeling; lexicographic product
2000 MR Subject Classification
1
05C15; 05C78
Introduction
Graphs considered here are all connected, finite, undirected, and without loops unless stated otherwise. For a real number s, the symbol ⌊s⌋ denotes the greatest integer which is not greater than s. A path with n vertices is called an n-path and denoted by Pn . Given a graph G = (V, E), a graph labeling is a bijective mapping f : E → ∑ {1, 2, · · · , |E|}. For each vertex u of G, the vertex-sum ωf (u) at u is defined as ωf (u) = f (e), where E(u) is the set e∈E(u)
of edges incident to u. For simplicity, ωf (u) is denoted by ω(u) if there is no confusion. In 1990, Hartsfield and Ringel[9] introduced the definition of antimagic graph, which states that a graph is called antimagic if there is a graph labeling f such that ωf (u) ̸= ωf (v) for any two distinct vertices u, v ∈ V (G). They also proposed the following conjecture. Conjecture
[9]
.
Every connected graph other than K2 is antimagic.
The most significant progress on this problem is the result of Alon et al[1] , which states the existence of a constant C such that if G is an n-vertex graph with δ(G) ≥ C log n, then G is antimagic. Since then, many classes of graphs have been proved to be antimagic. For example, the antimagicness of regular graphs have been obtained by Chang, Liang, Pan and Zhu[6] and by B´erczi, Bern´ath and Vizer[5] independently. In addition, the antimagicness concerning trees[11, 12] , Cartesian product of graphs[13, 19] , join graphs[4, 20] , generalized pyramid graphs[2] , and directed graph[10] have been proved. Recently, Arumugam, Premalatha and Baˇ ca introduced the local antimagic labeling of graphs. For more information about the antimagic graphs, a survey paper by Gallian[8] is referred. For n ≥ 3, a generalized magic matrix is an arrangement of numbers from 1 to n2 in an n × n matrix, with each number occurring exactly once, such that the sums of all rows and columns are identical. The following Lemma will be useful in the present paper. Manuscript received May 7,
Data Loading...
