Olga O'Mahony, Rachel Quinlan

National University of Ireland, Galway

olga.omahony@nuigalway.ie, rachel.quinlan@nuigalway.ie

A directed graph is primitive of exponent t if it contains walks of length t between all pairs of vertices, and t is minimal with this property. Moreover, it is exponent-critical if the deletion of any arc results in an imprimitive graph or in a primitive graph with strictly greater exponent. We establish necessary and sufficient conditions for the Kronecker product of a pair of graphs to be exponent-critical of prescribed exponent, defining some refinements of the concept of exponentcriticality in the process.

Keywords: primitive graph, exponent, graph Kronecker product

Mathematics Subject Classification : 05C20, 05C38

DOI: 10.5614/ejgta.2019.7.2.10

1. Introduction

A directed graph Γ is called primitive if there exists a positive integer t with the property that for all vertices u and v of Γ, there exists a walk of length t from u to v in Γ. The least such t is called the exponent of Γ. This article is concerned with primitive graphs that are exponent-critical in the sense that deletion of any arc would result either in a primitive graph with increased exponent or in an imprimitive graph. In particular, we consider the behaviour of this critical property and some variants under the Kronecker product of graphs.

This article extends some work that is reported in the 2017 PhD thesis [12] of the first author, whose theme is the study of finite edge-minimal undirected graphs of exponent 2, referred to as

Received: 4 June 2018, Revised: 27 April 2019, Accepted: 19 May 2019.

me2-graphs. In an undirected me2-graph, every pair of distinct vertices has at least one neighbour, but this property does not survive deletion of an edge. A motivation for the study of this property is provided by the famous Erdos-R ¨ enyi-S ´ os Theorem or Friendship Theorem [3], which classifies ` finite undirected graphs with the friendship property, namely that every pair of distinct vertices has exactly one shared neighbour. The Friendship Theorem states that a finite graph with this property is a union of triangles that all share a single vertex and are otherwise disjoint, often referred to as a windmill. For undirected graphs, the friendship property may be expressed as the statement that there is a unique walk of length 2 from every vertex to every other. In a me2 graph, it is not necessarily the case every pair of distinct vertices is connected by a unique walk of length 2, but such pairs are sufficiently abundant that every edge is involved in the unique walk of length 2 between some pair of vertices. Thus the undirected me2-property may be regarded as a generalization of the friendship property. It is established in [12] that undirected me2-graphs are plentiful, for example in the sense that every graph of order n is an induced subgraph of a me2 graph of order at most 3n + 2. A detailed analysis of embeddings of trees as induced subgraphs of me2-graphs is given in [13].

Considerable effort has been devoted to extending the Friendship Theorem in numerous directions. The formulation of the friendship property in terms of unique paths of length 2 has the advantages of admitting an obvious adaptation to the directed setting, and a natural extension to primitive graphs of exponent greater than 2. The problem of classifying directed graphs of order n in which there is a unique directed walk of length t from u to v for every pair of distinct vertices u and v was first investigated by Lam and Van Lint in [8], with the additional stipulation that the graph contains no closed walk of length t. A graph of this type has exponent t + 1 (provided that n ≥ 3) and need not be exponent-critical, as the examples in [8] demonstrate. Such a graph has adjacency matrix A satisfying A^t = J −In, where J is the n×n matrix whose entries are all equal to 1. Results on the identification and classification of (0, 1)-matrices satisfying this equation, and their corresponding graphs, can be found in [15] and [17] (for example).

The me2-property, which like the friendship property was first formulated for undirected graphs of exponent 2, also admits straightforward adaptations to the directed context and to arbitrary exponent. We will abbreviate the property of being exponent-critical of exponent t as the metproperty. A directed graph Γ of exponent t has the met-property if for every arc e of Γ there is a pair (u, v) of (not necessarily distinct) vertices such that every walk of length t from u to v in Γ includes the arc e. Thus the deletion of any arc from Γ results in a graph that does not have exponent t. This does not necessarily require that all or many pairs of vertices are connected by unique walks of length t, or that every arc belongs to a such a unique walk, but it requires a prevalence of pairs (u, v) without arc-disjoint t-walks from u to v. The adjacency matrix A of a met-graph is a (0, 1)-matrix for which A^t is positive, but B^t has a zero entry for every matrix B obtained from A by replacing a single 1 with a zero.

Kim, Song and Hwang determine the least possible number of edges in a primitive undirected graph of specified order and exponent in [6] and [7], and provide a corresponding analysis for directed graphs in the case of exponent 2. In many cases they identify all graphs in which these minima are attained, which obviously belong to the general class of exponent-critical (directed or undirected) primitive graphs. In the case of undirected graphs of exponent 2 and odd order n, they show that the minimum possible number of edges is ³ 2 (n − 1) and that this minimum is uniquely

attained by the windmill on n vertices. Thus the work of Kim et al. connects to the Friendship Theorem in a natural way.

Another familiar theme to which the concept of exponent-criticality is related is the analogous property for diameter. The diameter of a (strongly) connected graph G is the minimum over all ordered pairs (u, v) of vertices in G of the length of the shortest path from u to v in G. A connected graph is called diameter-critical if the deletion of any arc either disconnects the graph or leaves a graph of strictly higher diameter. The study of diameter-critical graphs originated in the 1960s (see for example [14], [11]) and has been a subject of the attention of numerous authors, mostly in the undirected setting. An up to date summary of the literature on this general topic can be found in a recent survey by Haynes et al [4].

The theme of this article is exponent-criticality for finite primitive graphs and its behaviour under the Kronecker product. The article is organised as follows. Section 2 provides relevant background information on primitivity and on the Kronecker product of graphs. In Section 3 we define a minimally primitive graph and characterize minimally primitive Kronecker products. The main technical content is in Section 4, which discusses conditions under which the Kronecker product of a pair of graphs is exponent-critical, and in the process introduces some refinements of the key property, of possible independent interest. In Section 5 we specialize some of the results of Section 4 to the relatively uncomplicated case of exponent 2.

We use the following terminology, notation and conventions. Graphs are assumed to be finite and are generally considered to be directed, except in Section 5 which includes a discussion of undirected graphs of exponent 2. In a directed graph, an arc is an ordered pair of vertices, respectively referred to as the initial and terminal vertices. We only consider graphs without loops, which means that the initial and terminal vertices of an arc are always distinct. When there is a need to specify the initial and terminal vertices, we will write the arc e = (u, v) as u → v or as e : u → v.

An undirected graph may be considered to be a directed graph in which v → u is an arc whenever u → v is an arc. In this situation we refer to the pair of arcs u → v and v → u as an edge and consider edges to be unordered pairs of vertices, writing e = uv where necessary to indicate that the edge e consists of the vertices u and v. The degree of a vertex in an undirected graph is the number of edges incident with that vertex. In an directed graph, the outdegree and indegree of a vertex v are respectively the number of arcs having v as initial or terminal vertex. If e is an arc (or an edge) in a graph Γ, then Γ\e denotes the graph obtained from Γ by deleting e.

A walk of length k from u to v in a graph G is a sequence u0, . . . , u^k of vertices, where u⁰ = u, u^k = v and uⁱ → ui+1 is an arc of G for i = 0, . . . , k − 1. A walk of length k involves k arcs and is referred to as a k-walk. The length of a walk P in a graph Γ is denoted lΓ(P). A path is a walk in which no vertex appears more than once. A circuit is a walk in which the first and last vertices coincide. A cycle is a circuit in which the only repetition of vertices is that the first and last coincide. A directed graph is strongly connected if it possesses a walk from u to v for every pair (u, v) of vertices, and minimally strongly connected if this property does not survive the deletion of any arc. The distance from u to v in a graph Γ is the length of a shortest walk from u to v in Γ, denoted dΓ(u, v).

2. Primitivity and Kronecker Products

Definition 2.1. Let Γ¹ and Γ² be directed graphs. The Kronecker product Γ¹ ⊗ Γ² is the directed graph with vertex set V (Γ1) × V (Γ2), in which (u, x) → (v, y) is an arc if and only if u → v is an arc in Γ¹ and x → y is an arc in Γ2.

The Kronecker product of graphs is also known by other names, including the direct product and tensor product; it corresponds to the matrix Kronecker product when graph data are encoded in adjacency matrices. If e : u → v and e : x → y are arcs of Γ¹ and Γ2, we will when convenient denote the arc (u, x) → (v, y) of Γ¹ ⊗ Γ² by (e, f).

Definition 2.2. A directed graph Γ is primitive if there is a positive integer t with the property that given any vertices x and y in Γ (not necessarily distinct), there is a directed walk of length t from x to y in Γ. The least t for which this holds is called the exponent of Γ, denoted exp(Γ).

We mention here some elements of the theory of primitive graphs, and refer to [1] for a detailed discussion. Clearly a primitive graph must be strongly connected. The converse is not true, as demonstrated for any integer n ≥ 2 by the graph consisting of a single directed cycle of length n. Let A be the adjacency matrix of a directed graph Γ. For a positive integer t, the entries of A^t count directed walks between pairs of vertices in Γ; thus Γ is primitive if and only if A^t is positive for some t, and the least t for which this occurs is the exponent of Γ.

If Γ is a primitive graph of exponent t with vertices u and v, then there is a walk of length k from u to v for every integer k with k ≥ t; this is equivalent to the observation that if A^t is positive for some non-negative matrix A, then all subsequent powers of A are positive also.

A graph is primitive if and only if it is strongly connected and the greatest common divisor of the lengths of its directed circuits (or equivalently cycles) is 1. The greatest common divisor of the lengths of the directed circuits of a strongly connected graph Γ is called the index of imprimitivity of Γ, denoted by µ(Γ). If u and v are vertices of Γ and P¹ and P² are directed walks from u to v in Γ, then by concatenating both P¹ and P² with a walk from v to u we can observe that the lengths of P¹ and P² are congruent modulo µ(Γ). If µ(Γ) > 1 it is then immediate that Γ cannot be primitive, since there is no t with the property that Γ contains a walk of length t from u to v for all k ≥ t. Moreover, given vertices u and v, there exists an integer Nuv with the property that every integer that exceeds Nuv and is congruent modulo µ(Γ) to dΓ(u, v) occurs as the length of some Γ-walk from u to v.

The characterization of primitivity in terms of cycle lengths takes a particularly simple form for undirected graphs. Since every (non-null) undirected graph possesses 2-cycles, an undirected graph (on at least two vertices) is primitive if and only if it possesses a cycle of odd length. Equivalently, an undirected graph is imprimitive if and only if it is bipartite, in which case its index of imprimitivity is 2.

We note the following necessary and sufficient conditions on the factors Γ¹ and Γ² in order for the Kronecker product Γ¹ ⊗ Γ² to be strongly regular or primitive.

Theorem 2.1. Let Γ¹ and Γ² be strongly connected graphs. Then

1. Γ¹ ⊗ Γ² is strongly connected if and only if µ(Γ1) and µ(Γ2) are relatively prime.

2. Γ¹ ⊗ Γ² is primitive if and only if both Γ¹ and Γ² are primitive. In this case the exponent of Γ¹ ⊗ Γ² is the maximum of the exponents of Γ¹ and Γ2.

Proof. The first item is Theorem 2 of [10]. We do not provide a detailed proof, but remark that the necessity of the condition is clear; let d = gcd(µ(Γ1), µ(Γ2)) and suppose that d > 1. There exists a pair (u, v) of vertices of Γ for which l^Γ1 (Puv) ≡ 0 mod d for every walk Puv from u to v in Γ1, and there exists a pair (x, y) of vertices of Γ² for which l^Γ2 (Pxy) ≡ 1 mod d for every walk Pxy from x to y in Γ2. Then there is no walk from (u, x) to (v, y) in Γ¹ ⊗ Γ2.

The sufficiency of the condition follows from the Chinese Remainder Theorem, along with the fact that every sufficiently large integer in the congruence class of d^Γ1 (u, v) modulo µ(Γ1) is the length of a Γ1-walk from u to v, and the analogous statement for x and y in Γ2.

For (2), suppose that Γ¹ ⊗ Γ² is primitive of exponent t. Let u, v be vertices of Γ¹ and let x, y be vertices of Γ2. The projections on Γ¹ and Γ² of a t-walk from (u, x) to (v, y) in Γ¹ ⊗ Γ² are t-walks from u to v and from x to y in Γ¹ and Γ2, respectively. Thus both Γ¹ and Γ² are primitive of exponent at most t, and exp(Γ¹ ⊗ Γ2) ≥ max(exp Γ1, exp Γ2).

On the other hand suppose that Γ¹ and Γ² are primitive, and let t be the greater of their exponents. Let (u, x) and (v, y) be vertices of Γ¹ ⊗ Γ2. There exist walks of length t from u to v in Γ¹ and from x to y in Γ2, which can be paired to produce a walk of length t from (u, x) to (v, y) in Γ¹ ⊗ Γ2. Thus Γ¹ ⊗ Γ² is primitive of exponent at most t.

Theorem 2.1 shows that the property of strong connectedness is not preserved by the Kronecker product of directed graphs, whereas the property of primitivity is. For undirected graphs, the first part of Theorem 2.1 amounts to the statement that the Kronecker product of two undirected graphs is connected if and only if both graphs are connected and at least one of them is primitive (or equivalently at most one is bipartite).

3. Minimally primitive graphs

Definition 3.1. A directed graph Γ is minimally primitive if Γ is primitive, and the deletion of any arc from Γ leaves an imprimitive graph.

Every arc in a strongly connected directed graph belongs to a directed cycle, and a directed graph is primitive if and only if the greatest common divisor of its cycle lengths is 1. If a graph Γ is minimally primitive, then for every arc e : u → v of Γ, at least one of the following occurs:

• there is no walk from u to v in Γ\e;
• there is a prime p with the property that the length of every cycle of Γ that does not include e is a multiple of p.

The class of minimally primitive graphs includes all primitive graphs with the property that deletion of an arc always leaves a graph that is not strongly connected. Such graphs are called minimally strongly connected, and it is shown in [1] that the maximum possible exponent of a minimally strongly connected primitive graph of order n is n ² − 4n + 6. Examples of minimally primitive graphs that are not minimally strongly connected include the Wielandt graphs. For n ≥ 3, the

maximum possible exponent of a primitive graph of order n is n ² − 2n + 2 and the Wielandt graph Wⁿ is the unique graph that attains this bound [16], [5]. It has n + 1 arcs and consists of a directed cycle of length n and an additional arc u → v, where the distance from u to v in the directed n-cycle is 2. Thus Wⁿ consists of an n-cycle and a (n − 1)-cycle that share n − 2 arcs; it is clearly primitive since n and n − 1 are relatively prime. It is minimally primitive, since deletion of the unique chord in the n-cycle leaves a single cycle of length n, and deletion of any other arc leaves a graph that is not strongly connected.

From any finite primitive graph Γ we may obtain a minimally primitive graph of the same order, by repeating the step of deleting an arc. The outcome of this process depends on the choice of deletion at each step, and its exponent is not determined by Γ and typically exceeds that of Γ. The following example shows a primitive graph of order 5 and its two minimally primitive subgraphs of order 5, which have different exponents but have the same number of arcs.

Example 3.1.

The graph G of Figure 1 is primitive of exponent 8. Deletion of the arc x¹ → x³ leaves a graph of exponent 14; deletion of the arc x⁵ → x³ leaves the Wielandt graph W⁵ which is primitive of exponent 17, and deletion of any other arc leaves an imprimitive graph.

Figure 1. A minimally primitive graph.

We have the following condition for minimal primitivity of a Kronecker product.

Theorem 3.1. Let Γ¹ and Γ² be directed graphs. Then Γ¹ ⊗ Γ² is minimally primitive if and only if both Γ¹ and Γ² are primitive and at least one of them is minimally primitive.

Proof. Suppose that Γ¹ and Γ² are primitive and that Γ¹ is minimally primitive. Then Γ¹ ⊗ Γ² is primitive by Theorem 2.1. Let e : (u, x) → (v, y) be an arc of Γ¹ ⊗ Γ2, and let e¹ denote the arc u → v of Γ1. Either Γ1\e¹ has no walk from u to v or Γ1\e¹ is strongly connected but imprimitive. In the first case, (Γ¹ ⊗ Γ2)\e has no walk from (u, z) to (v, z) for any vertex z of Γ2. In the second case, let d be the greatest common divisor of the cycle lengths in Γ1\e1; note d > 1 since Γ1\e¹ is imprimitive. The projection on Γ¹ of any cycle in (Γ¹ ⊗ Γ2)\e is a circuit in Γ1\e1. Thus the length of every cycle in (Γ¹ ⊗ Γ2)\e is a multiple of d. In neither case is (Γ¹ ⊗ Γ2)\e primitive, and we conclude that Γ¹ ⊗ Γ² is minimally primitive.

Now suppose that Γ¹ ⊗ Γ² is minimally primitive. Then Γ¹ and Γ² are primitive by Theorem 2.1. Suppose that neither of them is minimally primitive, and let e¹ and e² be arcs of Γ¹ and Γ²

respectively for which Γ1\e¹ and Γ2\e² are primitive graphs. Then (Γ1\e1) ⊗ (Γ2\e2) is primitive by Theorem 2.1. Since (Γ1\e1) ⊗ (Γ2\e2) is a subgraph of (Γ¹ ⊗ Γ2)\(e1, e2) with the same vertex set, it follows that (Γ¹ ⊗ Γ2)\(e1, e2) is primitive also, whence Γ¹ ⊗ Γ² is not minimally primitive. This contradiction completes the proof.

4. Exponent-critical graphs

If a directed graph Γ is primitive but not minimally so, then it has an arc e whose deletion leaves a primitive graph. In this case the exponent of Γ\e is at least equal to that of Γ and may be higher, as Example 3.1 shows. We consider graphs which are primitive and arc-minimal with respect to their exponent, in the sense that upon deletion of any arc, the property of primitivity is either lost or it is retained but with increased exponent. We refer to such graphs as exponent-critical, and for ease of exposition we introduce some further terminology.

Definition 4.1. A primitive graph Γ has the me^t (minimal exponent t) -property, or is a met-graph, if Γ is exponent-critical of exponent t, i.e. if Γ has exponent t and there is no arc e of Γ for which Γ\e is primitive of exponent t.

Definition 4.2. For a positive integer k, the directed graph Γ is k-arc-essential if Γ is primitive of exponent at most k and there is no arc e of Γ for which Γ\e is primitive with exponent at most k.

The distinction between the properties described in Definitions 4.1 and 4.2 may not be immediately obvious. A met-graph is a graph of exponent t that is t-arc-essential, and a k-arc-essential graph is one in which every arc is required for the existence of walks of length k between all pairs of vertices. A k-arc-essential graph need not have exponent k, as the graph G of Example 3.1 demonstrates. Deletion of the arc x¹ → x³ from G leaves a graph of exponent 14; deletion of the arc x³ → x⁵ leaves a graph of exponent 17, and deletion of any other arc breaks the primitivity (and the strong connectedness). Since G has exponent 8 it possesses a walk of length 8 from every vertex to every vertex; however this property is not shared by G\e for any arc e of G. Thus G is an me8-graph that is k-arc-essential for every k in the range 8 to 13. It is not 14-arc-essential, since the arc x¹ → x³ is not required for the existence of walks of length 14 between all pairs of vertices.

If the graph Γ is k-arc-essential, then for every arc e of Γ, there is pair u and v of vertices in Γ for which every k-walk from u to v in Γ includes the arc e. In a k-arc-essential graph, walks of length k exist from every vertex to every vertex, but this property does not survive the deletion of an arc. Every minimally primitive graph of exponent t is a met-graph, but a met-graph need not be minimally primitive. It is possible for a met-graph Γ to have the property that Γ\e is primitive (of exponent exceeding t) for every arc e. For example the complete loopless directed graph on 3 vertices is a me2-graph in which the deletion of any arc yields a me3-graph.

Lemma 4.1. Let Γ be a primitive graph of exponent t, that is k-arc-essential for some k ≥ t. Then, Γ is a met-graph.

Proof. We require to show that Γ is t-arc-essential. Suppose not, and let e be an arc of Γ for which Γ\e is primitive of exponent t. Then Γ\e possesses k-walks from every vertex to every vertex, contrary to the hypothesis that Γ is k-arc essential.

It follows from the argument of Lemma 4.1 that a k-arc-essential graph of exponent t is k 0 arc-essential for all k 0 in the range t to k. If Γ is minimally primitive of exponent t, then it is k-arc-essential all k ≥ t. If Γ is a met-graph that is not minimally primitive, then Γ is k-arcessential for all k in the range t to t ⁰ − 1 where t 0 is the minimum exponent of Γ\e, over all arcs e of Γ for which Γ\e is primitive.

We refer to a walk of length k from a vertex u to a vertex v in a graph Γ as a unique k-walk if it is the only k-walk from u to v in Γ. If every arc of a primitive graph Γ of exponent t belongs to some unique t-walk, then Γ is a met-graph. The met-property in general does not require that every arc belong to a unique t-walk. In fact the graph G of Example 4.1 below is a me12-graph in which there is no unique 12-walk.

We now consider conditions under which the Kronecker product of a pair of graphs is exponentcritical, and hence k-arc-essential at least for some value of k. Suppose that Γ¹ and Γ² are graphs for which Γ¹ ⊗ Γ² is k-arc-essential for a positive integer k. By Theorem 2.1, both Γ¹ and Γ² are primitive of exponent at most k. Let u → v and x → y be arcs of Γ¹ and Γ² respectively, so that (u, x) → (v, y) is an arc of Γ¹ ⊗ Γ2. Then there exist vertices (u 0 , x⁰ ) and (v 0 , y⁰ ) in Γ¹ ⊗ Γ² for which every walk of length k from (u 0 , x⁰ ) to (v 0 , y⁰ ) in Γ¹ ⊗ Γ² includes the arc (u, x) → (v, y). This is equivalent to the statement that there is an integer i in the range 1 to k with the property that u → v is the ith arc in every k-walk from u 0 to v 0 in Γ1, and x → y is the ith arc in every k-walk from x 0 to y 0 in Γ2. Thus Γ¹ and Γ² are both k-arc-essential, and moreover all arcs of Γ¹ and all arcs of Γ² satisfy compatibility conditions on the positions in which they are required for k-walks in Γ¹ and Γ2.

This observation motivates the following definitions.

Definition 4.3. Let Γ be a primitive graph of exponent at most k and let e be an arc of Γ.

• The arc e is k-required in position i in Γ if there exist vertices u and v (not necessarily distinct) in Γ with the property that every k-walk from u to v in Γ has e as its ith arc.
• The arc e is k-required in fixed position in Γ if e is k-required in position i for some i.
• We write

\[C_{\Gamma}^{k}(e) = \{i \in \{1, \dots, k\} : e \text{ is } k\text{-required in position } i\}.\]

and refer to C k Γ (e) as the k-fixed position set of e.

• The graph Γ is k-arc-static if C k Γ (e) is non-empty for every arc e of Γ, i.e. if every arc is k-required in fixed position.

Clearly a k-arc-static graph must be k-arc-essential. The following example shows that a karc-essential graph need not be k-arc-static.

Example 4.1. The graph G of Figure 2 is clearly primitive, since it is strongly connected and possesses directed cycles of lengths 2, 3 and 5.

A matrix computation confirms that the exponent of G is 12 (note that G has no 11-walk from x⁵ to x8). Since G is minimally strongly connected, it is a me12-graph. We claim that the arc x¹ → x⁴ is not 12-required in fixed position in G, whence C 12 ^G (x¹ → x4) is empty and G is not

Figure 2. A 12-arc-essential graph that is not 12-arc-static.

12-arc-static. To see this we partition the vertex set of G as the union of A = {x1, x2, x3} and B = {x4, x5, x6, x7, x8, x9}.

First suppose that xⁱ and x^j are vertices of A. If xⁱ = x^j , then there is a 12-walk from xⁱ to xi that involves only arcs of the triangle T induced on A. If xⁱ → x^j is an arc, then there is a 10-walk from xⁱ to x^j that involves only arcs of T and includes the vertex x¹ at least three times. This may be extended to a 12-walk by inserting the pair x4, x¹ after any of these appearances of x1. Similarly if the shortest path from xⁱ to x^j has length 2, then (for example) there is a 8-walk from xⁱ to x^j that involves only arcs of T and includes x¹ three times. We may insert the segment x4, x9, x4, x¹ after any appearance of x1, to obtain different 12-paths from xⁱ to x^j not requiring the arc x¹ → x⁴ in the same position.

If xⁱ and x^j are vertices of B, then it is easily confirmed that there is a 12-walk from xⁱ to x^j in G that involves only arcs of the subgraph induced on B.

If xⁱ ∈ B and x^j ∈ A, then there is a 12-walk from xⁱ to x^j in G that does not involve the arc x¹ → x4. To see this note that there is a walk of even length at most 10 from xⁱ to x^j , possibly involving a circuit of the triangle T, and including the arc x⁴ → x¹ once. Such a walk can be augmented to one of length 12 by inserting the necessary repetitions of the pair x9, x⁴ after the appearance of x4.

Finally suppose that xⁱ ∈ A and x^j ∈ B. We claim that the arc x¹ → x⁴ is not needed in fixed position for a 12-walk from xⁱ to x^j . There exist walks of lengths i, i + 3 and i + 6 from xⁱ to x4, each involving the arc x¹ → x⁴ exactly once. It is straightforward to check that for each x^j in B, at least two of these three walks from xⁱ to x⁴ may be extended to walks from xⁱ to x^j , that have even length not exceeding 12, and that involve the arc x¹ → x⁴ exactly once each, in different positions. Since any walk of even length may be extended to one of length 12 using the 2-cycle at x9, this ensures that the arc x¹ → x⁴ is not 12-required in fixed position for a walk from a vertex of A to a vertex of B. We conclude that C 12 ^G (x¹ → x4) is empty and G is not 12-arc-static.

The exponent of a k-arc-static graph is at most k but may be less, as demonstrated by the Wielandt graphs.

Example 4.2.

The Wielandt graph W4, of exponent 10, is shown in Figure 3. We claim that each of the five arcs of W⁴ is 11-required in fixed position in W4. With the exception of x³ → x1, each arc of W⁴ involves

a vertex with either an indegree or an outdegree of 1, and is therefore k-required either in position 1 or position k, for all k ≥ 10. For the arc x³ → x1, we note that the unique 11-walk in W⁴ from x¹ to x³ involves this arc in positions 3, 6 and 9. Thus, W⁴ is 11-arc-static. The graph W⁴ is also 12-arc-static, but not 13-arc-static. For n ≥ 3, the Wielandt graph Wⁿ is k-arc-static for all k in the range n ² − 2n + 2 to n ² − n.

Figure 3. The Wielandt graph W4.

The following observation is an analogue of Lemma 4.1 for the property of k-arc-staticity.

Lemma 4.2. Let Γ be a primitive graph of exponent t. If Γ is k-arc-static for some k ≥ t, then Γ is t-arc-static.

Proof. Let e be an arc of Γ. Then e is k-required in position i in Γ, for some i ∈ {1, . . . , k}. Let u and v be vertices of Γ with the property that every k-walk from u to v in Γ has e as its ith arc. Let u, u1, . . . , uk−1, v be such a k-walk. If i ≤ t, then every t-walk from u to u^t has e as its ith arc, so e is t-required in position i in Γ. If i > t, then every t-walk from ui−^t to uⁱ has e as its final arc, so e is t-required in position t in Γ.

In particular it follows from Lemma 4.2 (and its proof) that a k-arc-static graph of exponent t is a met-graph and is k 0 -arc-static for all k 0 in the range t to k. It is possible for a graph of exponent t to be k-arc-static for all k ≥ t; for example the graph of order 5 that consists of a 3-cycle and a 4-cycle sharing a single arc has exponent 12 and has the property that every arc either originates at a vertex of outdegree 1 or terminates at a vertex of indegree 1. Thus, every arc is k-required either in position 1 or in position k, for all k ≥ 12.

We now return to the task of articulating conditions under which the Kronecker product of a given pair of graphs is exponent-critical, beginning with a reformulation of our earlier observations in the language of Definition 4.3. Before stating necessary and sufficient conditions for the Kronecker product of a pair of graphs to be k-arc-essential, we recall that the definitions of the terms k-arc-essential and k-arc-static include the stipulation that the graph in question is primitive of exponent at most k.

Theorem 4.1. Let \(\Gamma_1\) and \(\Gamma_2\) be directed graphs each having at least one arc. Then

• 1. \(\Gamma_1 \otimes \Gamma_2\) is a k-arc-essential graph if and only if both \(\Gamma_1\) and \(\Gamma_2\) are k-arc-static and the k-fixed position sets of all arcs of \(\Gamma_1\) and \(\Gamma_2\) have pairwise non-empty intersection.
• 2. If \(\Gamma_1 \otimes \Gamma_2\) is k-arc-essential then it is k-arc-static.

Proof. The "only if" direction of 1. is proved by the remarks preceding Definition 4.3. For the "if" direction, suppose that \(\Gamma_1\) and \(\Gamma_2\) satisfy the hypotheses. Then \(\Gamma_1 \otimes \Gamma_2\) is primitive of exponent at most k by Theorem 2.1. Let (e,f) be an arc of \(\Gamma_1 \otimes \Gamma_2\), where e and f are the corresponding arcs of \(\Gamma_1\) and \(\Gamma_2\), and let \(i \in C^k_{\Gamma_1}(e) \cap C^k_{\Gamma_2}(f)\). Then there exist vertices u,v of \(\Gamma_1\) and x,y of \(\Gamma_2\) for which every k-walk from u to v in \(\Gamma_1\) includes the arc e in position i, and every k-walk from x to y in \(\Gamma_2\) includes the arc f in position f. It follows that every f-walk from f to f in position f in position f in position f in position f in position f in position f in f in position f in f in position f in f in position f in f in position f in f in position f in f in position f in f in f in position f in f in f in position f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f in f

A particular case in which the conditions of Theorem 4.1 are satisfied is where there is some \(i \in \{1, \ldots, k\}\) for which every arc of \(\Gamma_1\) and every arc of \(\Gamma_2\) is k-required in position i in \(\Gamma_1\) or \(\Gamma_2\) respectively. This is the case where the intersection over all arcs e of \(\Gamma_1\) and all arcs f of \(\Gamma_2\) of the sets \(C^k_{\Gamma_1}(e)\) and \(C^k_{\Gamma_2}(f)\) is non-empty. This can occur only if both \(\Gamma_1\) and \(\Gamma_2\) are k-uniformly static as defined below.

Definition 4.4. Let \(\Gamma\) be a primitive graph of exponent at most k, and let \(r \in \{1, ..., k\}\). We say that \(\Gamma\) is (k, r)-uniformly static if every arc e of \(\Gamma\) is k-required in position r. We say that \(\Gamma\) is k-uniformly static if it is (k, r)-uniformly static for some r.

The following is an immediate consequence of Theorem 4.1. We note in particular that if there is some r for which \(\Gamma_1\) and \(\Gamma_2\) are both (k, r)-uniformly static, then \(\Gamma_1 \otimes \Gamma_2\) is k-arc-essential.

Corollary 4.1. Let \(\Gamma_1\) and \(\Gamma_2\) be primitive graphs of exponent at most k, and let \(r \in \{1, ..., k\}\). Then \(\Gamma_1 \otimes \Gamma_2\) is (k, r)-uniformly static if and only if both \(\Gamma_1\) and \(\Gamma_2\) are (k, r)-uniformly static.

Example 4.3. The graph G shown in Figure 4 has exponent 5 and is (5,3)-uniformly static. Thus \(G \otimes G\) is also a (5,3)-uniformly static graph, by Corollary 4.1.

Figure 4. A (5,3)-uniformly static graph.

A k-arc-static graph need not be uniformly static, as the following example shows.

Example 4.4. The graph G of Figure 5 has exponent 6 and is minimally strongly connected, so it has the me6-property. By inspecting 6-walks between vertices of G, we may note for example that for each vertex xⁱ there is a 6-walk from x¹ to xⁱ in G that has x¹ → x⁴ as its first arc, which means that the arc x¹ → x² is not 6-required in position 1, and 1 6∈ C 6 ^G(x¹ → x2). The elements of C 6 ^G(e) for each arc e of G are listed below.

Figure 5. A 6-arc-static graph that is not uniformly static.

This example shows that the k-arc-static Kronecker product of a pair of graphs need not be kuniformly static; G is a graph of exponent 6 that is 6-arc-static but not uniformly so. The pairwise intersections C 6 ^G(e) ∩ C 6 ^G(f) are non-empty for all arcs e and f of G, so the Kronecker product G ⊗ G is a me6-graph that is 6-arc-static, by Theorems 4.1 and 2.1. However the intersection over all arcs e of G of the sets C 6 ^G(e) is empty, so G ⊗ G is not 6-uniformly static.

We now consider the class of graphs that are uniformly static for all feasible parameters, which we will refer to as strong met-graphs. Suppose that Γ is a t-arc-essential graph of order at least 3, with the additional property that C t Γ (e) = {1, . . . , t} for every arc e of Γ, so that Γ is (t, r) uniformly static for every r ∈ {1, . . . , t}. Then from Theorem 4.1 it follows that Γ ⊗ Γ 0 is t-arcessential (and t-arc-static) for every t-arc-static graph Γ 0 . In this situation we note that the exponent of Γ must be t. To see this let x be a vertex of Γ of outdegree at least 2 (such a vertex must exist since x is primitive). Let x → y and x → y ⁰ be distinct arcs of Γ, and let z be any vertex. If the exponent of G is less than t, then there exists a (t − 1)-walk from y 0 to z in Γ and so there exists a t-walk from x to z that has x → y 0 as its first arc. Since this statement holds for every vertex z of Γ, we reach the contradiction that the arc x → y is not t-required in position 1. The conclusion is that a t-arc-essential graph in which every edge is t-required in every position must have exponent t, and we make the following definition.

Definition 4.5. A primitive directed graph Γ has the strong met-property, or is a strong met-graph, if it is (t, r)-uniformly static for every r in the range 1, . . . , k.

By the above comments, a strong met-graph is necessarily a met-graph. We now present examples to demonstrate the existence of strong met-graphs for all t ≥ 2. Our examples consist of separate families for even and odd exponent.

Figure 6. The strong me5-graph G10.

Example 4.5. Strong met-graphs of even exponent.

Let t be an even positive integer. Let Ct+1 be the undirected cycle of length t + 1, interpreted as a directed graph consisting of two oppositely directed cycles on the same vertex set. We label the vertices of Ct+1 as x1, . . . , xt+1, where xⁱ → x^j is an arc if and only if |i − j| = 1 or |i − j| = t. If xⁱ and x^j are distinct vertices, there are arc-disjoint paths from xⁱ to x^j that follow the two distinct directed (t + 1)-cycles. One of these has even length at most t, and may be extended if necessary to a t-walk from xⁱ to x^j by adding repetitions of a 2-cycle at any vertex. There exists a t-walk in Ct+1 from each vertex to itself, since t is even and every vertex belongs to a 2-cycle. Hence the exponent of Ct+1 is at most t. Finally, there is no walk of length t − 1 from any vertex to itself in Ct+1, so the exponent of Ct+1 is exactly t.

If i and j differ by 1 (or t), then there is a unique t-walk from xⁱ to x^j in t, that involves t successive arcs of one of the two t-cycles. Inspection of these unique t-paths confirms that every arc is t-required in every fixed position, and so Ct+1 is a strong met-graph.

Example 4.6. Strong met-graphs of odd exponent.

For t odd, t ≥ 3, define the directed graph G2^t of order 2t as follows.

• The vertex set of G2^t is {x1, . . . , x^t , y1, . . . , yt}.
• The arc set of G2^t is defined as follows:
  • For i = 1, . . . , t − 1, xⁱ → xi+1 and yⁱ → yi+1 are arcs; x^t → x¹ and y^t → y¹ are arcs;
  • For i = 2, . . . , t, xⁱ → xi−¹ and yⁱ → yi−¹ are arcs;
  • The remaining arcs are x¹ → y^t and y¹ → x^t .

The example G10, for t = 5, is shown in Figure 6.

In our discussion of the graph G2^t we consider xⁱ and yⁱ to be defined for all integers i and we identify xⁱ with x^{i 0}, and yⁱ with y^{i 0}, whenever i and i 0 are congruent modulo t. This notational device is convenient for our discussion of properties of G2^t .

Since \(G_{2t}\) is strongly connected and has a 4-cycle on \(\{x_1,y_t,y_1,x_t\}\) and also has a cycle of odd length t, it is clearly primitive. Its exponent cannot be less than t, since for example the shortest walk from \(x_{\frac{t+1}{2}}\) to \(y_{\frac{t+1}{2}}\) has length t. On the other hand it is straightforward to confirm that \(G_{2t}\) contains t-walks from every vertex to every vertex.

To verify that the strong me_t-property holds in \(G_{2t}\), we consider arcs of three different types.

• 1. The arcs \(x_i \to x_{i+1}\) and \(y_i \to y_{i+1}\)For \(k \in \{1, \dots, t\}\) the arc \(x_i \to x_{i+1}\) is required in position k for the unique t-walk in \(G_{2t}\) from the vertex \(x_{i-t+1}\) to itself. A similar observation applies to \(y_i \to y_{i+1}\).
• 2. The arcs \(x_i \to x_{i-1}\) and \(y_i \to y_{i-1}\), for \(i \in \{2, \dots, t\}\)Let \(k \in \{1, \dots, t\}\). If \(i + k \le t + 1\), the arc \(x_i \to x_{i-1}\) is required in position k for the unique t-walk in G from \(x_{i+k-1}\) to \(y_{i+k-1}\). If i + k > t + 1, then \(x_i \to x_{i-1}\) is required in position k for the unique t-walk in \(G_{2t}\) from \(y_{i+k-t-1}\) to \(x_{i+k-t-1}\). Similar analysis applies to \(y_i \to y_{i-1}\).
• 3. For \(k \in \{1, ..., t\}\) the arc \(x_1 \to y_t\) is t-required in position k for the unique t-walk in \(G_{2t}\) from \(x_k\) to \(y_k\), and \(y_1 \to x_t\) is similarly required for \(y_k\) to \(x_K\).

Thus \(G_{2t}\) is a strong me_t-graph.

It follows from Corollary 4.1 that the Kronecker product of two graphs is a strong \(me_t\)-graph if and only if both factors are strong \(me_t\)-graphs. We conclude this section with a summary of criteria for a Kronecker product to be exponent-critical with specified additional properties. We recall from Theorem 2.1 that if the maximum of the exponents of two primitive graphs is t, then their Kronecker product is primitive of exponent t.

Theorem 4.2. Let \(\Gamma_1\) and \(\Gamma_2\) be primitive graphs each of order at least 2, and let t be a positive integer.

• 1. \(\Gamma_1 \otimes \Gamma_2\) is a \(me_t\)-graph if and only if \(t = \max\{\exp(\Gamma_1), \exp(\Gamma_2)\}\) and \(C_{\Gamma_1}^t(e) \cap C_{\Gamma_2}^t(f)\) is non-empty for all arcs e of \(\Gamma_1\) and f of \(\Gamma_2\).
• 2. \(\Gamma_1 \otimes \Gamma_2\) is (t,r)-uniformly static if and only if \(\Gamma_1\) and \(\Gamma_2\) are both (t,r)-uniformly static.
• 3. \(\Gamma_1 \otimes \Gamma_2\) is a \(me_t\)-graph if either \(\Gamma_1\) or \(\Gamma_2\) is a strong \(me_t\)-graph and the other is t-arc-static.
• 4. \(\Gamma_1 \otimes \Gamma_2\) is a strong \(me_t\)-graph if and only if both \(\Gamma_1\) and \(\Gamma_2\) are strong \(me_t\)-graphs.

5. Graphs of exponent 2

In graphs of exponent 2, many of the special properties discussed in Section 4 turn out to be equivalent, which allows for a much more concise version of Theorem 4.2 in this special case, particularly in the undirected setting. Let \(\Gamma\) be a (directed) graph with the me₂-property, and let \(e: u \to v\) be an arc of \(\Gamma\). Deletion of e would either leave a graph with no 2-walk from u to some vertex x, or a graph with no 2-walk from some vertex y to v. Thus e is either 2-required in position 1 for a walk originating at u, or 2-required in position 2 for a walk terminating at v. In particular every me₂-graph is 2-arc-static.

Now suppose that \(\Gamma_1\) and \(\Gamma_2\) are graphs for which \(\Gamma_1 \otimes \Gamma_2\) has the me₂-property. Since a graph without loops cannot have exponent 1, it follows from Theorem 4.2 that \(\Gamma_1\) and \(\Gamma_2\) are me₂-graphs.

Suppose that neither Γ¹ nor Γ² has the strong me2-property, and let e be an arc of Γ¹ which is 2-required only in one position, say in position 1. Then every arc of Γ² is 2-required in position 1 by Theorem 4.2, so Γ² is (2, 1)-uniformly static. Since Γ² does not have the strong me2-property, it has an arc f for which C 2 Γ² (f) = {1}, whence Γ¹ is also (2, 1)-uniformly static by the same reasoning.

Theorem 4.2 has the following formulation for t = 2.

Theorem 5.1. Let Γ¹ and Γ² be directed graphs. Then Γ¹ ⊗ Γ² has the me2-property if and only if Γ¹ and Γ² are me2-graphs and either

• at least one of Γ¹ and Γ² has the strong me2-property, or
• Γ¹ and Γ² are both (2, r)-uniformly static for the same r ∈ {1, 2}.

We remark that the inclusion of the second case is necessary in Theorem 5.2; it is possible for a directed graph of exponent 2 to be (2, 1)-uniformly static and not (2, 2)-uniformly static. The least possible order of such a graph is 6 and the unique example (up to isomorphism) of order 6 is shown below.

Example 5.1.

The graph G of Figure 7 is a me2-graph in which every arc is the first arc in some unique 2-path. However, the arc x³ → x¹ (for example) is not required in position 2 for a 2-walk from any vertex to x1. By Theorem 5.2, G ⊗ G is a me2-graph.

Moreover, G ⊗ G is (2, 1)-uniformly static but not (2, 2)-uniformly static.

Figure 7. A me2-graph that is (2, 1)-uniformly static but not (2, 2)-uniformly static.

In a directed graph Γ of exponent 2, the me2-property is equivalent to the statement that every arc belongs to a unique 2-walk in Γ.

We now turn attention to undirected graphs of exponent 2. In general, care is needed in adapting the definition of the met-property to the context of undirected graphs, since the two interpretations below may need to be distinguished.

Definition 5.1. Let Γ be a primitive undirected graph of exponent t.

• If the undirected graph Γ\e is imprimitive or primitive of exponent exceeding t for every edge e of Γ, we say that Γ has the undirected met-property.
• If Γ has the met-property when interpreted as a directed graph (in which v → u is an arc whenever u → v is), we say that Γ has the directed met-property.

It is clear that any undirected graph with the directed met-property also possesses the undirected met-property. That the two do not coincide in general is confirmed by the following example.

Example 5.2. The undirected graph shown in Figure 8 is primitive of exponent 3, and has the undirected me3-property but not the directed me3-property. Deletion of the arc u → v leaves a directed graph that is primitive of exponent 3. Deletion of the edge uv leaves a primitive undirected graph of exponent 4. The key point here is that the edge uv is 3-required only for a walk from w to w, and there are two such walks that traverse this edge in opposite directions. Thus one of the two arcs between u and v can be deleted with no effect on the primitivity status of the graph or on the exponent.

Figure 8. The undirected me3-property is weaker than the directed me3-property.

We now show that in the special case of undirected graphs of exponent 2, we need not distinguish between the directed and undirected versions of the me2-property.

Lemma 5.1. Let Γ be a primitive undirected graph of exponent 2 that has the undirected me2 property. Then Γ has the directed me2-property.

Proof. Let u → v be an arc of Γ and let e denote the edge uv of Γ. We need to show that the directed graph obtained from Γ by deleting the arc u → v is not primitive of exponent 2.

Since Γ has the undirected me2-property, deletion of the edge e from Γ would leave a graph with a vertex x sharing no neighbour with v, or a vertex y sharing no neighbour with u. In the first case, x, u, v is the unique 2-walk from x to v in Γ, and in the second case u, v, y is the unique 2-walk from u to y in Γ. In either case the arc u → v is required for the existence of 2-walks between all pairs of vertices in Γ. We conclude that Γ has the directed me2-property.

Since every pair of vertices in a primitive undirected graph of exponent 2 has a common neighbour, every edge belongs to a triangle and every vertex has degree at least 2. It follows that no edge can be required for a 2-walk from any vertex to itself, and every edge of an undirected me2-graph is included in the unique 2-walk between two distinct vertices.

For clarity we reformulate the me2-property for undirected graphs as follows.

Definition 5.2. The undirected graph Γ has the me2-property if Γ is primitive of exponent 2, and for every edge uv of Γ there exists a vertex x whose only common neighbour with v is u, or a vertex y whose only common neighbour with u is v.

This characterization recalls the original friendship property, which is the condition that every 2-path in an undirected graph is the unique 2-path between its endpoints. The me2-property for undirected graphs does not require that all 2-paths are unique, but that unique 2-paths are sufficiently plentiful that every edge belongs to one.

Theorem 4.2 admits further refinement for undirected graphs of exponent 2, after the following observation.

Lemma 5.2. Let Γ be an undirected me2-graph. Then Γ is (2, 1)-uniformly static if and only if Γ is (2, 2)-uniformly static.

Proof. Suppose that Γ is (2, 1)-uniformly static and let u → v be an arc of Γ. We require to show that u → v is the latter arc in some unique 2-walk in Γ. Since v → u is an arc of Γ, and Γ is (2, 1)-arc static, v → u is the inital arc of the unique 2-walk in Γ from v to some vertex w. Since Γ is undirected, it follows that w, u, v is the unique 2-walk from w to v in Γ, hence that u → v is 2-required in position 2 in Γ and Γ is (2, 2)-uniformly static.

An immediate consequence of Lemma 5.2 is that an undirected me2-graph Γ has the strong me2-property if it is 2-uniformly static. This means that every edge uv is included in a unique 2-path originating at u and one originating at v. Example 5.1 shows that the hypothesis that G is undirected is necessary in Lemma 5.2. We may reformulate Definition 4.5 as follows, for undirected graphs of exponent 2.

Definition 5.3. An undirected graph Γ has the strong me2-property if Γ has exponent 2 and for every edge uv of Γ, there exist vertices x and y (not necessarily distinct) such that u is the unique common neighbour of x and v in Γ, and v is the unique common neighbour of y and u in Γ.

Examples of infinite families of undirected strong me2-graphs include the windmills and the Kneser graphs with parameters (3r, r) for r ≥ 1. The Kneser graph Kn(3r, r) is the graph of order 3r r whose vertices represent the r-element subsets of a set of 3r elements, and in which two vertices are adjacent if the subsets that they represent are disjoint. More generally any undirected graph of exponent 2 in which every edge belongs to a unique 3-cycle is a strong me2-graph, although strong me2-graphs need not have this property. It is shown in [12] that every complete graph arises as an induced subgraph of a strong me2-graph.

An infinite family of undirected graphs that have the me2-property but not the strong me2 property is the collection {Gⁿ : n ≥ 4} defined as follows. The vertex set of Gⁿ is {x1, x2, . . . xn},

and the vertices x¹ and x² are both adjacent to all others. For i ≥ 3, xⁱ is adjacent only to x¹ and x2. It is easily checked that Gⁿ is a me2-graph. For i ≥ 3, inspection of the edge x1xⁱ shows that Gⁿ is not a strong me2-graph. The vertex xⁱ is not the unique common neighbour of x¹ and any other vertex of Gn, whereas x¹ is the unique common neighbour of xⁱ and x2.

Theorem 4.2 takes the following form for undirected me2-graphs. We remark that this theorem bears a structural resemblance to the undirected version of Theorem 2.1, which states that the Kronecker product of undirected graphs is connected if and only if both factors are connected and at least one is primitive, and that the product is primitive if and only if both factors are primitive.

Theorem 5.2. Let Γ¹ and Γ² be undirected graphs each of order at least 2. Then

• 1. Γ¹ ⊗Γ² is a me2-graph if and only if both Γ¹ and Γ² are me2-graphs and at least one of them is a strong me2-graph.
• 2. Γ¹ ⊗ Γ² is a strong me2-graph if and only if both Γ¹ and Γ² are strong me2-graphs.

Acknowledgement

The authors are grateful to Niall Madden for contributing Example 5.2. This article was written during the second author's 2018 sabbatical visit to the Department of Mathematics and Statistics at Memorial University of Newfoundland, whose hospitality is gratefully appreciated.

References

• [1] R.A. Brualdi and J.A. Ross, On the exponent of a primitive, nearly reducible matrix, Math. Oper. Res., 5(2):229–241, 1980.
• [2] F.R.K. Chung, Graphs with small diameter after edge deletion, Discrete Appl. Math., 37/38:73–94, 1992.
• [3] P. Erdos, A. R ¨ enyi and V.T. S ´ os, On a problem of graph theory, ´ Studia Sci. Math. Hungar., 1:215–235, 1966.
• [4] T.W. Haynes, M.A. Henning, L.C. van der Merwe and A. Yeo, Progress on the Murty-Simon Conjecture on diameter-2 critical graphs: a survey, J. Comb. Optim., 30(3):579–595, 2015.
• [5] J.C. Holladay and R.S. Varga, On powers of non-negative matrices, Proc. Amer. Math. Soc., 9:631–634, 1958.
• [6] Byeong Moon Kim, Byung Chul Song, and Woonjae Hwang, Nonnegative primitive matrices with exponent 2, Linear Algebra Appl., 407:162–168, 2005.
• [7] Byeong Moon Kim, Byung Chul Song, and Woonjae Hwang, Primitive graphs with given exponents and minimum number of edges, Linear Algebra Appl., 420(2-3):648–662, 2007.
• [8] C.W.H. Lam and J.H. van Lint, Directed graphs with unique paths of fixed length, J. Combinatorial Theory Ser. B, 24(3):331–337, 1978.

• [9] Po-Shen Loh and Jie Ma, Diameter critical graphs, J. Combin. Theory Ser. B, 117:34–58, 2016.
• [10] M.H. McAndrew, On the product of directed graphs, Proc. Amer. Math. Soc., 14:600–606, 1963.
• [11] U.S.R. Murty, On critical graphs of diameter 2, Math. Mag., 41:138–140, 1968.
• [12] O. O'Mahony, Edge-minimal graphs of exponent 2, PhD thesis, National University of Ireland, Galway, 2017.
• [13] O. O'Mahony and R. Quinlan, Edge-minimal graphs of exponent 2, Linear Algebra Appl., 542:66–83, 2018.
• [14] O. Ore, Diameters in graphs, J. Combinatorial Theory, 5:75–81, 1968.
• [15] Tian Ming Wang and Ke Quan Ding, On some solutions of A^k = J − I, J. Math. Res. Exposition, 7(4):665–667, 1987.
• [16] H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z., 52:642–648, 1950.
• [17] Yaokun Wu and Qiao Li, An approach to solving A^k = J−I, Linear Algebra Appl., 373:121– 142, 2003, Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002).