Exponents of a class of special three-colored primitive digraphs with $n$ vertices in graph theory

1.   Introduction

Graph theory originated from the famous problem of the seven bridges of Königsberg. In 1736, Euler used abstract analysis to prove that the seven bridges problem of Königsberg had no solution, which was the first graph theory problem and also marked the birth of graph theory as a discipline. With the development of graph theory, it has become a widely applied branch of mathematics. There are traces of graph theory and its applications in various fields such as mathematics, computer science, and biological science.

The graph coloring problem is one of the classic problems in the field of combinatorial optimization, which has penetrated into multiple disciplines such as physics, chemistry, biology, electronics, economics, management, and computer science. More and more people are interested in and attach importance to graph theory. Coloring the edges (arcs) or vertices of a graph can often be associated with a matrix, thereby effectively solving the problem. We conducted research on the complementarity spectrum of the directed graph and Gromov hyperbolicity of Johnson and Kneser graphs and obtained some mathematical conclusions ^[1,2]. Some research has been conducted on issues such as metal halide perovskites, perovskite light-emitting diodes, and predicting electronic band structures of quantum-confined nanostructures in physics, and some of these problems have been solved through the application of graph coloring ^[3,4,5]. We consider each atom in a molecule as a vertex in the graph and the chemical bonds between atoms as edges in the graph. By coloring the graph, we can solve the problem of molecular structure in biology and chemistry ^[6,7,8,9]. In fact, algorithms can be optimized through graph coloring problems. In ^[10], graph invariants were used to quantitatively characterize the topological properties of complex networks. In ^[11,12], hybrid heuristic coloring algorithms, intelligent optimization algorithms, and heuristic algorithms that are applicable to both large-scale and small-hard graphs were presented. The results obtained have guiding significance for the research of related problems.

In this article, we establish corresponding relationships between nonnegative matrices and their adjoint directed graphs, or between directed graphs and their adjacent matrices. By coloring the edges (arcs) of the directed graph, we discuss and find the upper bound of the exponent in the primitive case, providing reference for the application of graph coloring problems. The following basic concepts are given.

A three-colored digraph $D$ is a graph with a direction and whose arc contains three colors (usually red, yellow, and blue). If $D$ has a sequence of vertices $v_{1}v_{2}\cdots v_{t}v_{t+1}$, then it is a walk from $v_{1}$ to $v_{t+1}$ of length $t$; if $v_{1}v_{2}\cdots v_{t}v_{t+1}$ are different, then it is a path from $v_{1}$ to $v_{t+1}$ of length $t$^[13]. The arcs of the same walk or path can be the same color or different colors. $D$ is a strongly connected graph if any two vertices can be reached by a walk. $\nu$'s decomposition vector is expressed as $(u(\nu), v(\nu), w(\nu))$ or $(u(\nu), v(\nu), w(\nu))^{T}$, then $\nu$ is said to be an $(u(\nu), v(\nu), w(\nu))$-walk, where $u(\nu)$, $v(\nu)$, and $w(\nu)$ represent respectively the numbers of red arcs, the numbers of yellow arcs and the numbers of blue arcs in $\nu$.

For any $(v_{i}, v_{j})$, there exists an $(h_{1}, h_{2}, h_{3})$-walk from $v_{i}$ to $v_{j}$, where $h_{1}$, $h_{2}$ and $h_{3}$ are nonnegative integers and

then the minimum value of $h_{1}+h_{2}+h_{3}$ is the primitive exponent of $D$, denoted as $exp(D)$.

Let

be the set of cycles, $M_{1}$ be the cycle matrix of $D$. Thus

for some nonnegative integers $u_{i}, v_{i}, w_{i}$ $(i = 1, 2, \cdots, t)$, where the $i$th column of $M_{1}$ represents the decomposition vector of the $\gamma_{i}$-cycle. The content of $M_{1}$, usually denoted as content$(M_{1})$, is defined to be 0 if $r(M_{1}) < 3$; otherwise, content$(M_{1})$ is defined to be the greatest common factor of all $3 \times 3$ minors of $M_{1}$, where $r(M_{1})$ is the rank of $M_{1}$.

Lemma 1. ^[14] If $D$ is a three-colored primitive digraph, then $D$ is strongly connected and

Combinatorial mathematics is an important branch of mathematics that is used widely in many fields such as computer networks, economics, operations research, information coding, etc. Nonnegative matrix theory and graph theory are two important research contents in combinatorial mathematics. In solving the exponential problems of nonnegative matrices, the equivalent relation is often established with their associated digraphs so as to solve the problems of nonnegative matrices with associated digraphs. At present, the research on single nonnegative matrices and nonnegative matrix pairs is basically perfect, and it is an inevitable trend to extend the research to nonnegative matrix clusters. Analogous to the correspondence between a single matrix and its associated digraphs. Three-colored digraphs are associated digraphs of nonnegative matrix clusters, and there is a one-to-one correspondence between them. According to the simple and intuitionistic characteristics of the graph, we can use three-colored digraphs to solve the problems related to the primitive exponent of nonnegative matrix clusters.

Up to now, some achievements have been made on the primitive exponents of nonnegative matrix pairs (or two-colored digraphs) and nonnegative matrix clusters (or three-colored digraphs). There are some basic concepts of graph theory that are needed to carry out the research in this paper ^[13,14]. Gao and Shao are the earliest experts in the study of primitive exponents of two-colored digraphs in China, and the studying method of primitive exponents of two-colored digraph has a good reference effect for the research of three-colored digraphs ^[15]. The range of primitive exponent is found by taking a class of two-colored digraph (or nonnegative matrix pairs) as an example, respectively, and the coloring of the arcs that reach the upper and lower bounds of the exponent are given ^{[15,16,17,18,19]}. By coloring all arcs, the exponent set of the corresponding digraph is found ^[20,21]. With the in-depth study of the primitive exponents of two-colored digraphs (or nonnegative matrix pairs), most of the problems of primitive exponents have been solved. The research on the extension of two-colored digraphs to three-colored digraphs is a relatively new field and has achieved few achievements. Some representative classes of three-colored digraphs are selected respectively for research; some upper bounds of exponents and the extremal three-colored digraphs are found on the premise of primitives ^{[22,23,24,25]}.

For $n\geq5$, we study a class of three-colored digraphs whose uncolored digraph is shown in Figure 1.

Obviously, $D$ is strongly connected. It is known that the coloring of the arcs in the 3-cycle can be the same or different. That is to say, the three arcs can be one color, two colors, or three colors in the 3-cycle. If the three arcs in the 3-cycle can contain only one color, and $\hbox{content}(M_{1})$ must be a multiple of 3 at this point, so

and $D$ is non-primitive. If the coloration of all three arcs in the 3-cycle is different, that is, the path is decomposed into $(1, 1, 1)^{T}$, which has been discussed ^[22]. If the three arcs in the 3-cycle have two different patterns, then the walks can be decomposed into six possibilities, specifically $(0, 1, 2)^{T}$ or $(0, 2, 1)^{T}$ or $(1, 0, 2)^{T}$ or $(1, 2, 0)^{T}$ or $(2, 0, 1)^{T}$ or $(2, 1, 0)^{T}$.

Since the calculation methods of the six coloring cases of the three arcs are similar when two colors are included in the 3-cycle, in this paper, we only research when there are zero red arcs, one yellow arc, and two blue arcs in the 3-cycle, that is, the decomposition vector of the 3-cycle is $(0, 1, 2)^{T}$ on the basis of ^[22]. In this case, we can assume $D$'s cycle matrix

for some nonnegative integers $a$–$d$.

From Figure 1, the $n$-cycle and 3-cycle in $D$ have two common arcs, $v_{n}\rightarrow v_{1}$ and $v_{1}\rightarrow v_{2}$. The coloring of arcs $v_{n}\rightarrow v_{1}$ and $v_{1}\rightarrow v_{2}$ can be the same or different in a 3-cycle. The $n$-cycle and $(n-3)$-cycle in $D$ only have five non-common arcs $v_{n}\rightarrow v_{1}\rightarrow v_{2} \rightarrow v_{3} \rightarrow v_{4}$ and $v_{n}\rightarrow v_{4}$. Thus

2.   The primitive conditions

This section gives the primitive conditions that $D$ needs to satisfy. Combined with Figure 1, for the sake of discussion, we can assume

where $k$ is an integer and

Theorem 1. If $D$ is primitive, then

Proof. From formula (1), we have

According to Lemma 1, we know if

then

Therefore,

□

Theorem 2. If $a = c-1$, then $D$ is primitive,

$n$ is not a multiple of 3, and

Proof. Because

from formulas (1) and (2), we can see

According to Lemma 1, we know if

then

Since $n$ is not a multiple of 3, we can discuss it in the following five cases:

(1) If $k = 0$, then

So $D$ is primitive and

(2) If $k = 1$, then

So $D$ is primitive and

(3) If $k = 2$, then

So $D$ is primitive and

(4) If $k = 3$, then

So $D$ is primitive and

(5) If $k = 4$, then

So $D$ is primitive and

□ Similarly, we can obtain Theorems 3–7.

Theorem 3. If

then

and $D$ is non-primitive.

Theorem 4. If

then $D$ is primitive,

$n$ is not a multiple of 3 and

Theorem 5. If

then $D$ is primitive,

$n$ is not a multiple of 3, $c$ is not a multiple of 2 and

Theorem 6. If

then

and $D$ is non-primitive.

Theorem 7. If

then $D$ is primitive,

$n$ is not a multiple of 3, $c$ is not a multiple of 2, and $b = d$.

3.   The upper bound on the exponents of $D$

Because of the complexity of the calculation, we will use "maple" software to calculate all primitive exponents of three-colored digraphs $D$, compare them, and find the maximal primitive exponent for the case

Since the calculation method is similar, we shall only find out the upper bound on the exponents when

Theorem 8. If

and $D$ is primitive, then

Proof. For every pair of vertices $(v_{i}, v_{j})$ in $D$, we say that $p_{v_{i}v_{j}}$ represents the shortest path from $v_{i}$ to $v_{j}$, and denote

and

We can always find the same walk to go from $v_{i}$, along $p_{v_{i}v_{j}}$ to $v_{j}$, and the numbers of revolutions around the $n$-cycle, the $(n-3)$-cycle, and the $3$-cycle are $p_{1}$ times, $p_{2}$ times, and $p_{3}$ times, respectively. □

If

from Theorem 2, we have

that is

Combined with Figure 1, the $n$-cycle has one more red arc than the $(n-3)$-cycle, so we can see that $v_{n}\rightarrow v_{4}$ is a red arc. The following situations are discussed from

and

(1) According to formula 1, if

then

and

From formula (3), we know that the elements in the cycle matrix $M_{3}$ are nonnegative, so

The positivity or negativity of each element in the matrix $M_{3}^{-1}$ depends on the value of $c$. Therefore, we can determine the symbol of each element in $M_{3}^{-1}$ that does not include $-c+2$. The value of $-c+2$ is directly related to the size of $c$, which is discussed in the following three cases.

(ⅰ) $c = 1$.

According to formulas (3) and (4), we have

and

At this point, we know

Taking

and

we see that

Noting that

Obviously, we can obtain

This gives

(ⅱ) $c = 2$.

According to formulas (3) and (4), we have

and

At this point, we know

Taking

and

we see that

Noting that

If $x = 2$, then

and $p_{v_{i}v_{j}}$ must contain the arc $v_{n}\rightarrow v_{4}$, and the initial and terminal vertices of $p_{v_{i}v_{j}}$ must be on the ($n-3$)-cycle. If $x = 1$, then

If

then $x\geq0$, $z\geq0$. If

then $x\geq0$, $y\geq0$. Obviously, we can obtain

This gives

(ⅲ) $3\leq c\leq\frac{2n-5}{3}$.

At this point, we know

According to formulas (3) and (4), taking

and

we see that

Noting that

If $x = c$, then

and $p_{v_{i}v_{j}}$ must contain the arc $v_{n}\rightarrow v_{4}$, and the initial and terminal vertices of $p_{v_{i}v_{j}}$ must be on the ($n-3$)-cycle. If $x = c-1$, then

and

If

then $x\geq0$, $z\geq0$. If

then $x\geq0$, $y\geq0$. Obviously, we can obtain $p_{1}\geq0$, $p_{2}\geq0$, and $p_{3}\geq0$. This gives

Let $f_{1}(c)$ be a function of $c$ and

then

and $f_{1}(c)$ is an increasing function. Because

then

(2) According to formula (1) and Theorem 2, if

then

and

From formula (5), we know that the elements in the cycle matrix $M_{6}$ are nonnegative, so

The positivity or negativity of each element in the matrix $M_{6}^{-1}$ depends on the value of $c$. So, based on the range of values for $c$ and $n\geq5$, we can judge the sign of each element in $M_{6}^{-1}$.

Taking

and

we see that

Noting that

If $x = c$, then

and

and $p_{v_{i}v_{j}}$ must contain the arc $v_{n}\rightarrow v_{4}$, the initial and terminal vertices of $p_{v_{i}v_{j}}$ must be on the ($n-3$)-cycle. If

then

and

If

then $x\geq0$, $z\geq0$. If

then $x\geq0$, $y\geq0$. Obviously, we can obtain

This gives

Let $f_{2}(c)$ be a function of $c$ and

then

and $f(c)$ is an increasing function. Because

then

In summary, the upper bounds of all primitive exponents of

can be obtained. Thus

Comparing all the values of $\hbox{exp}(D)$, we obtain

4.   The extremal digraphs characterization

We will give the coloring of the arcs of $D$ such that the equality holds, that is, the extremal digraphs with the maximal primitive exponent.

Theorem 9. If

and $D$ is primitive, then

if and only if the $\frac{n+1}{3}$ yellow arcs are consecutive on the $n$-cycle.

Proof. Obviously, the corresponding cycle matrix is formula (5). We can see that if the equality in Theorem 8 holds, then

This completes the proof. □

Sufficiency. Suppose $(h_{1}, h_{2}, h_{3})$ is a 3-tuple of nonnegative integers, and there is an $(h_{1}, h_{2}, h_{3})$-walk from $v_{i}$ to $v_{j}$ for every pair of vertices $(v_{i}, v_{j})$.

Taking $v_{i}$ and $v_{j}$ to be the same vertex on the $n$-cycle, then there exist nonnegative integers $\mu_{1}$–$\mu_{3}$ satisfying

We can suppose that the starting vertex of $\frac{n+1}{3}$ continuous yellow arcs on the $n$-cycle is $v_{i}$ and the ending vertex is $v_{j}$. Combined with Figure 1, there is only one path from $v_{i}$ to $v_{j}$, and the vector of the walk is decomposed into $(0, \frac{n+1}{3}, 0)$. Thus

has a nonnegative integer solution that satisfies the conditions. Therefore,

Then

Similarly, we can suppose that the ending vertex of $\frac{n+1}{3}$ continuous yellow arcs on the $n$-cycle is $v_{i}$ and the starting vertex is $v_{j}$. Combined with Figure 1, there is only one path from $v_{i}$ to $v_{j}$, and the vector of the walk is decomposed into $(c-1, 0, \frac{2n+2}{3}-c)$. Thus

has a nonnegative integer solution that satisfies the conditions. Therefore,

Then

Thus

Let $f_{3}(c)$ be a function of $c$ and

then

and $f_{3}(c)$ is an increasing function. Because

then

Include proofs in the form

such that the equation is satisfied.

Necessity. We can use proof by contradiction. We just have to show

if there are no continuous yellow arcs of $\frac{n+1}{3}$ length.

In this case, there are at most $\frac{n-2}{3}$ long continuous yellow paths on the $n$-cycle. For every pair of vertices $(v_{i}, v_{j})$ in $D$, we say that $p_{v_{i}v_{j}}$ represents the shortest path from $v_{i}$ to $v_{j}$, and denote

We can always find the same walk to go from $v_{i}$, along $p_{v_{i}v_{j}}$ to $v_{j}$, and the numbers of revolutions around the $n$-cycle, the $(n-3)$-cycle, and the $3$-cycle are $p_{1}$ times, $p_{2}$ times, and $p_{3}$ times, respectively.

Taking

and

we see that

Noting that

If $x = c$, then

and

and $p_{v_{i}v_{j}}$ must contain the arc $v_{n}\rightarrow v_{4}$, the initial and terminal vertices of $p_{v_{i}v_{j}}$ must be on the ($n-3$)-cycle. If $x = c-1$, then

and

If

then $x\geq1$, or $z\geq1$. If

then

and

or

and

So we can obtain $p_{1}\geq0$, $p_{2}\geq0$, and $p_{3}\geq0$. This gives

Let $f_{4}(c)$ be a function of $c$ and

then

and $f_{4}(c)$ is an increasing function. Because

then

5.   Conclusions

On the basis of previous references, we study the primitive problems of a class of three-colored digraphs shown in Figure 1 when there are zero red arcs, one yellow arc, and two blue arcs in the 3-cycle. We discussed the coloring of Figure 1 in different situations, found the conditions that the primitive digraph needs to satisfy, and obtained Theorems 1–7. In the primitive state, the maximum primitive exponent of the three-colored digraphs was found when

and the conclusion of Theorem 8 was obtained. Finally, the extreme digraph that reaches the upper bound of the exponent was characterized, and Theorem 9 was given. The research methods and conclusions of this article provide reference for using digraph coloring to solve some problems in physics, computer science, biology, and other fields.

Author contributions

Meijin Luo: the conceptualization, proof techniques, checking the calculations, and writing the manuscript; Qiutao Qin: the collection and organization of literature, research analysis, and manuscript. All authors have read and approved the final published version of the manuscript.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was supported by the High-level Talent Start-up Project of Hechi University (No. 2022GCC008), National Natural Science Foundation of China (No. 31702049), Project of Young and Mid-aged College Teachers of Guangxi in 2024 (No. 2024KY0632) and Project of Hechi College (No. 2022YLXK001).

Conflict of interest

The authors declare that they have no conflicts of interest.