ON THE LEAST NUMBER OF EDGE OF PRIMITIVE GRAPHS WITH EXPONENTS EQUAL TO 3

SCIENCE AND INNOVATION INTERNATIONAL SCIENTIFIC JOURNAL VOLUME 4 ISSUE 11 NOVEMBER 2025 ISSN: 2181-3337 | SCIENTISTS.UZ 128 ON THE LEAST NUMBER OF EDGE OF PRIMITIVE GRAPHS WITH EXPONENTS EQUAL TO 3 R. Shamsiev Department of Mathematics and physics, Alfraganus University, Tashkent – 704414, Uzbekistan Abstract. This article considers the problem of finding the minimum number of vertices in primitive graphs with exponent three. First, a necessary condition for a graph with exponent three to be primitive is given. Next, the impossibility of constructing primitive graphs with exponent three from four and five vertices is proven. This proof is based on the fact that such graphs do not satisfy the necessary condition for being primitive with exponent three. Finally, a minimal graph with six vertices is constructed. Keywords: primitive graph, exponent, edge, vertex. Introduction The concept of primitivity was originally formulated for square matrices in [1]. If we consider a square matrix as the adjacency matrix of a graph, then the concept of primitivity naturally extends to graphs. Let us recall the necessary definitions. A non-negative square matrix 𝐴 is called primitive if there exists a natural number 𝑡 such that 𝐴𝑡 is positive. The minimum such value of 𝑡 is called the exponential of 𝐴 [1]. We follow the notation and terminology of graphs in [2]. A graph is a pair 𝐺 = (𝑉, 𝐸) of sets satisfuing 𝐸𝑉 × 𝑉; thus, the elements of 𝐸 are 2-element subsets of 𝑉. The elements of 𝑉 are the vertices of the gfraph 𝐺, the elements of 𝐸 are its edges. A route in graph 𝐺 is an alternating sequence of edge vertices 𝑤0, 𝑥1,𝑤1, … , 𝑤𝑛−1, 𝑥𝑛,𝑤𝑛; this sequence begins and ends with a vertex. This route connects vertices 𝑤0 and 𝑤𝑛 and can be denoted by (𝑤0, 𝑤1),(𝑤1, 𝑤2), …, (𝑤𝑛−1, 𝑤𝑛). The route is closed if 𝑤0= 𝑤𝑛 and open otherwise. A route is called a chain if all its edges are distinct, and a simple chain if all vertices are distinct. A closed chain is called a cycle. A closed route is called a simple cycle if all its 𝑛 vertices are distinct and 𝑛 ≥ 3. Denote by 𝐶𝑛 the graph consisting of a single simple cycle with 𝑛 vertices. Elements of the set 𝑉 are called vertices of graph 𝐺, and elements of 𝐸 are its edges. A vertex 𝑣 is by definition reachable from a vertex 𝑢 in 𝑘 ≥ 1 steps if there exists a sequence of nonrepeating adjacent edges (route) ,(𝑤1, 𝑤2), … , (𝑤𝑘−1, 𝑤𝑘) (in short records 𝑤0𝑤1𝑤2… 𝑤𝑘−1𝑤𝑘), where 𝑤0= 𝑢 and 𝑤𝑘= 𝑣. A graph 𝐺 = (𝑉,𝐸) on n vertices is primitive if there is a positive integer 𝑟 ≥ 2 such that for each pair of vertices 𝑢, 𝑣 of 𝐺, there is a walk of length 𝑟 from 𝑢 to 𝑣. Thus, every primitive graph is strongly connected (any two vertices are mutually reachable). The minimum value of such an integer, 𝑟, is the exponent, 𝑒𝑥𝑝(𝐺), of 𝐺. A number of works are devoted to the study of exponents of primitive graphs [3-6]. In [7], the problem of constructing minimal primitive extensions is considered. The problem of the largest number of vertices of primitive regular graphs with exponent 2 was considered in [8]. In [9], the minimum number ℎ(𝑛,𝑘) of edges of a simple graph 𝐺 on 𝑛 vertices with index 𝑘 was found, and all graphs with ℎ(𝑛,𝑘) edges were listed when 𝑘 is even. This note considers the problem of the smallest number of vertices in primitive graphs with exponent equal to 3. SCIENCE AND INNOVATION INTERNATIONAL SCIENTIFIC JOURNAL VOLUME 4 ISSUE 11 NOVEMBER 2025 ISSN: 2181-3337 | SCIENTISTS.UZ 129 Theorem 1. If 𝐺 is a primitive graph with exp(𝐺) = 3, then every edge of the graph 𝐺 is included in a quadrilateral. Proof. Consider two arbitrary adjacent vertices 𝑢, 𝑣. Between them there must be a route of length 3 that does not contain edge (𝑢, 𝑣). Consequently, there are two adjacent vertices, different from 𝑢 and 𝑣, 𝑥 and 𝑦, one of which is adjacent to vertex 𝑢, and the other to 𝑣. Thus, the edge (𝑢,𝑣) is included in the quadrangle formed by the vertices 𝑢, 𝑣, 𝑥 and 𝑦 (Fig. 1). Corollary 1. It is impossible to construct a primitive graph with exp(𝐺) = 3 from 4 vertices. Proof. Let the vertices 𝑢, 𝑣, 𝑥 and 𝑦 form a primitive graph with exp(𝐺) = 3. Then, by Theorem 1, this graph includes a quadrangle formed by the vertices 𝑢, 𝑣,𝑥 and 𝑦. But this quadrilateral is not primitive with exp(𝐺) = 3 (between non-adjacent vertices the route length is 2). If we connect non-adjacent vertices with an edge, we get a primitive graph with exp(𝐺) = 2 (Fig. 2 (a), (b), (c)). Corollary 2. It is impossible to construct a primitive graph with exp(𝐺) = 3 from 5 vertices. Proof. Quadrangle from Fig. 1 we add one vertex in different ways and analyze each case separately. 1) Add one vertex, connecting one of the vertices 𝑢, 𝑣, 𝑥 and 𝑦 with one edge. Then in all cases the necessary condition of Theorem 1 is not satisfied (Fig. 3), i.e. vertex (𝑢, 𝑤) is not included in the quadrilateral. 2) Let's add one vertex, connecting two vertices from 𝑢,𝑣, 𝑥 and 𝑦 with two edges (Fig. 4. (a), (b)). 𝑣 𝑥 𝑢 𝑦 Fig. 1. 𝑣 𝑥 𝑢 𝑦 𝑣 𝑥 𝑢 𝑦 𝑦 𝑣 𝑢 𝑥 Fig. 2. (a) (b) (c) 𝑣 𝑥 𝑢 𝑦 𝑤 Fig. 3. SCIENCE AND INNOVATION INTERNATIONAL SCIENTIFIC JOURNAL VOLUME 4 ISSUE 11 NOVEMBER 2025 ISSN: 2181-3337 | SCIENTISTS.UZ 130 (a) In this case, the edge (𝑤, 𝑦) does not belong to any quadrilateral, i.e. the necessary condition for the primitivity of a graph with exp(𝐺) = 3 is not satisfied. If in this graph we connect vertices 𝑦 and 𝑣 by an edge, then the necessary condition for the primitivity of the graph is satisfied for the edge (𝑤, 𝑦). But the resulting graph becomes a primitive graph with exp(𝐺) = 2. (b) The necessary primitivity condition is satisfied for all edges. But this is not enough for primitiveness. There is no route of length 3 between non-adjacent vertices. 1) If an edge (𝑣, 𝑤) is added, then between vertices 𝑣 and 𝑤 there will be no route of length 3, and any further addition of edges leads to a primitive graph with exp(𝐺)= 2 (Fig. 6(a)). 2) If he adds an edge (𝑣, 𝑦), then there will be no route between vertices 𝑣 and 𝑦, with a length of 3, and here, too, any further addition of edges leads to a primitive graph with exp(𝐺)= 2 (Fig. 6(b) )). Thus, we have considered all possible graphs with 5 vertices, all of which cannot be primitive graphs with exponent 3. Now let's move on to considering 6 vertex graphs. Consider a graph consisting of two quadrangles, one of which intersects the other diagonally (Fig. 5). This 6-vertex graph is primitive with exponent 3. Indeed, all vertices belong to quadrilaterals, i.e. the necessary condition of primitivity is satisfied. Further, routes between 𝑣 𝑥 𝑢 𝑦 𝑤 Fig. 4. 𝑣 𝑥 𝑢 𝑦 𝑤 Fig. 3. 𝑣 𝑥 𝑢 𝑦 𝑤 a) b) 𝑣 𝑥 𝑢 𝑦 𝑤 (a) 𝑣 𝑥 𝑢 𝑦 𝑤 (b) Fig. 5. 𝑣 𝑥 𝑢 𝑦 𝑧 𝑤 Fig. 6. SCIENCE AND INNOVATION INTERNATIONAL SCIENTIFIC JOURNAL VOLUME 4 ISSUE 11 NOVEMBER 2025 ISSN: 2181-3337 | SCIENTISTS.UZ 131 vertices z and y have lengths greater than 2. Let us indicate all routes between any vertices with length 3: 𝑢 → 𝑣:(𝑢, 𝑦),(𝑦, 𝑥),(𝑥, 𝑣); 𝑣 → 𝑤:(𝑣,𝑥),(𝑥,𝑧), (𝑧,𝑤); 𝑢 → 𝑥: (𝑢, 𝑦),(𝑦, 𝑧), (𝑧, 𝑥); 𝑥 → 𝑦:(𝑥, 𝑤),(𝑤, 𝑧), (𝑧, 𝑦); 𝑢 → 𝑦:(𝑢, 𝑣),(𝑣, 𝑥),(𝑥, 𝑦); 𝑥 → 𝑧: (𝑥, 𝑤),(𝑤,𝑦), (𝑦, 𝑧); 𝑢 → 𝑧: (𝑢, 𝑦),(𝑦,𝑤), (𝑤, 𝑧); 𝑥 → 𝑤: (𝑥,𝑦),(𝑦,𝑧), (𝑧, 𝑤); 𝑢 → 𝑤:(𝑢, 𝑣),(𝑣, 𝑥),(𝑥, 𝑤); 𝑦 → 𝑧: (𝑦, 𝑥),(𝑥, 𝑤), (𝑤,𝑧); 𝑣 → 𝑥:(𝑣,𝑢),(𝑢, 𝑦), (𝑦,𝑥); 𝑦 → 𝑤: (𝑦, 𝑧),(𝑧, 𝑥),(𝑥,𝑤); 𝑣 → 𝑦: (𝑣, 𝑥),(𝑥, 𝑧), (𝑧, 𝑦); 𝑧 → 𝑤: (𝑧, 𝑦),(𝑦, 𝑥),(𝑥, 𝑤); 𝑣 → 𝑧: (𝑣,𝑢),(𝑢, 𝑦),(𝑦, 𝑧); Conclusion Thus, we have proven that it is impossible to construct a primitive graph with exponent three from four or five vertices. Figure 6 shows a primitive graph with six vertices and exponent three. Based on the above statements, we can state the smallest number of vertices in primitive graphs with exponent three in the following theorem. Theorem 2. The smallest number of vertices of a primitive graph with exponent 3 is 6. REFERENCES 1. Wiеlandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. V.52. P.642–648. 2. Reinhard Diestel. Graph Theory. Electronic Edition 2000. Springer-Verlag New York 1997, 2000. 3. B. Liu, B.D. McKay, N.C. Wormald, K. Zhang, The exponent set of symmetric primitive (0, 1) matrices with zero trace // Linear Algebra Appl. 133 (1990) 121–131. 4. Jin M., Lee S. G., and Seol H. G. Exponents of r-regular primitive matrices. // Inform. Center Math. Sci., 2003, vol. 6, no. 2, pp. 51–57. 5. Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. № 2(11). С. 101–112. 6. Фомичев В. М., Авезова Я. Э. Точная формула экспонентов перемешивающих орграфов регистровых преобразований //Дискретный анализ и исследование операций. 2020. № 2(27). С. 117–135. 7. Салий В. Н. Минимальные примитивные расширения ориентирован-ных графов // Прикладная дискретная математика. 2008. № 1(1). С. 116–119. 8. Абросимов М.Б., Костин С.В., Лось И.В. О наибольшем числе вершин примитивных однородных графов порядка 2, 3, 4 с экспонентом, равным 2. // Прикладная дискретная математика. 2021. № 52. С. 97–104. 9. Byeong Moon Kim, Byung Chul Song, Woonjae Hwang. Primitive graphs with given exponents and minimum number of edges// Linear Algebra Appl. 420 (2007) 648–662.