Event Type:

Number Theory Seminar

Date/Time:

Tuesday, March 1, 2016 - 16:00 to 17:00

Location:

Gilkey 115

Guest Speaker:

Institution:

Willamette University

Abstract:

A graph $G$ is a $k$-prime product distance graph if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the product of at most $k$ primes. A graph has prime product number $\ppn(G)=k$ if it is a $k$-prime product graph but not a $(k-1)$-prime product graph. Similarly, $G$ is a prime $k$th-power graph if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the $k$th power of a prime.

We prove that $\ppn(K_n) = \lceil \log_2(n)\rceil - 1$, and that if $G$ is $k$-chromatic $\ppn(G) = \lceil \log_2(k)\rceil - 1$ or $\ppn(G) = \lceil \log_2(k)\rceil$. We also prove that $K_n$ is not a prime $k$th-power graph for any $k \geq 7$, even cycles are prime $k$th-power graphs for all positive integers $k$, and odd cycles are prime $k$th-power graphs for sufficiently large $k$.

We find connections between prime product and prime power distance graphs and the Twin Prime Conjecture, the Green-Tao Theorem, and Fermat's Last Theorem.

Host: