Connectedness of digraphs from quadratic polynomials

Suppose that $f (x) = x (x - k)$ , where $k$ is an odd positive integer. First, an infinite digraph $G_{k} = (V, E)$ is defined, where the vertex set is $V = ℤ$ and the edge set is $E = {(x, y) ∣ x, y \in ℤ, f (x) = f (2 y)}$ . Then the following results are proved: if $k = 1$ , then the digraph $G_{k}$ is weakly connected; if $p$ is a safe prime, i.e., both $p$ and $q = (p - 1) ∕ 2$ are primes, then the number $w_{p}$ of weakly connected components of the digraph $G_{p}$ is 2. Finally, a conjecture that there are infinitely many primes $p$ such that $w_{p} = 2$ is presented.

Keywords

connectivity, digraph, prime

Mathematical Subject Classification 2010

Primary: 05C25

Secondary: 05C40, 05C20

Milestones

Received: 2 February 2020

Revised: 10 March 2020

Accepted: 14 March 2020

Published: 30 March 2020

Communicated by Vadim Ponomarenko

Authors

Siji Chen
RDFZ Xishan AP Center RDFZ Xishan School Beijing China

Sheng Chen
Department of Mathematics Harbin Institute of Technology Harbin China

Vol. 13, No. 2, 2020

Siji Chen and Sheng Chen

Abstract

Keywords

Mathematical Subject Classification 2010

Milestones

Authors