On sets of integers with restrictions on their products

2014/04/24 by Michael Tait, Tait, Michael, Jacques Verstraete +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1404.6261

arxiv created 2014/04/24 · arxiv updated 2014/04/28

Abstract

A \em product-injective labeling of a graph G is an injection χ: V(G) → ℤ such that χ(u)χ(v) \not= χ(x)χ(y) for any distinct edges uv, xy∈ E(G). Let P(G) be the smallest N ≥ 1 such that there exists a product-injective labeling χ: V(G) → [N]. Let P(n,d) be the maximum possible value of P(G) over n-vertex graphs G of maximum degree at most d. In this paper, we determine the asymptotic value of P(n,d) for all but a small range of values of d relative to n. Specifically, we show that there exist constants a,b > 0 such that P(n,d) ∼ n if d ≤ √(n)(log n)^-a and P(n,d) ∼ nlog n if d ≥ √(n)(log n)^b.

Related

• Total vertex product irregularity strength of graphs
• Distance two labeling of direct product of paths and cycles
• A Study on the Product Set-Labeling of Graphs
• Maximizing the number of integer pairs summing to powers of 2 via graph labeling and solving restricted systems of linear (in)equations
• On an extremal problem for locally sparse multigraphs