Lambda number of the power graph of a finite group
- PDF / 334,791 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 101 Downloads / 229 Views
Lambda number of the power graph of a finite group Xuanlong Ma1
· Min Feng2 · Kaishun Wang3
Received: 28 November 2018 / Accepted: 13 January 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The power graph G of a finite group G is the graph with the vertex set G, where two distinct elements are adjacent if and only if one is a power of the other. An L(2, 1)-labeling of a graph is an assignment of labels from nonnegative integers to all vertices of such that vertices at distance two get different labels and adjacent vertices get labels that are at least 2 apart. The lambda number of , denoted by λ(), is the minimum span or range over all L(2, 1)-labelings of . In this paper, we obtain bounds for λ(G ) and give necessary and sufficient conditions when the bounds are attained. As applications, we compute the exact value of λ(G ) if G is a dihedral group, a generalized quaternion group, a P-group or a cyclic group of order pq n , where p and q are distinct primes and n is a positive integer. Keywords Power graph · L(2, 1)-labeling · λ-Number · Finite group Mathematics Subject Classification 05C25 · 05C78
1 Introduction All graphs considered in this paper are finite, simple and undirected. Let be a graph with the vertex set V () and the edge set E(). The distance between vertices x and y is the length of a shortest path from x to y in . For nonnegative integers j and k, an
B
Xuanlong Ma [email protected] Min Feng [email protected] Kaishun Wang [email protected]
1
School of Science, Xi’an Shiyou University, Xi’an 710065, China
2
School of Science, Nanjing University of Science and Technology, Nanjing 210094, China
3
School of Mathematical Sciences and Laboratory of Mathematics and Complex Systems, Beijing Normal University, Beijing 100875, China
123
Journal of Algebraic Combinatorics
L( j, k)-labeling of is a nonnegative integer-valued function f on V () such that | f (u)− f (v)| ≥ k whenever u and v are vertices of distance two and | f (u)− f (v)| ≥ j whenever u and v are adjacent. The span or range of f is the difference between the maximum and minimum values of f . The L( j, k)-labeling number λ j,k () of is the minimum span over all L( j, k)-labelings of . The classical work of the L( j, k)labeling problem is when j = 2 and k = 1. The L(2, 1)-labeling number of a graph is also called the λ-number of and denoted by λ(). The problem of studying L( j, k)-labelings of a graph is motivated by the radio channel assignment problem [17] and by the study of the scalability of optical networks [31]. In 1992, Griggs and Yeh [16] formally introduced the notion of the L(2, 1)labeling of a graph and showed that the L(2, 1)-labeling problem is NP-complete for general graphs. Georges and Mauro [12] later presented a generalization of the concept. The L( j, k)-labeling problem, in particular in the L(2, 1) case, has been studied extensively; see [13,14,27,32] for examples. Surveys of results and open questions on the L( j, k)-labeling problem can be fo
Data Loading...