Exponents of primitive directed Toeplitz graphs

ABSTRACT

Given disjoint non-empty subsets S and T of $\{1,\dots ,n-1\}$, a digraph D with the vertex set $\{1,2,\dots ,n\}$ is called a directed Toeplitz graph provided the arc $i\to j$ occurs if and only if $i-j\in S$ or $j-i\in T$. We investigate strong connectivity and primitivity of directed Toeplitz graphs. We prove that any primitive directed Toeplitz graph with $n\ge 6$ vertices has exponent at least 3 and for each $n\ge 6$, there is a primitive directed Toeplitz graph of order n which has exponent 3. By Wielandt's result, we know that $\exp \left(D\right)\le (n-1{)}^2+1$ for a primitive digraph D of order n. We characterize the primitive directed Toeplitz graph, for which the upper bound it attained.

Keywords:

• Directed Toeplitz graph
• Toeplitz matrix
• strongly connected graph
• primitive graph
• exponent
• Frobenius number

2010 Mathematics Subject Classifications:

• 05C20
• 05C50

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) [2016R1A5A1008055, NRF-2017R1E1A1A03070489 and NRF-2019R1A2C1007518] and the Ministry of Education of Korea [NRF-2016R1A6A3A11930452 and NRF-2019R1I1A1A01044161].