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

DOWNLOAD

REPORT


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