We extend the study of link-irregular graphs to directed graphs (digraphs), where a digraph is link-irregular if no two vertices have isomorphic directed links. We establish that link-irregular digraphs exist on n vertices if and only if n ≥ 5, and prove that their underlying graphs must contain 3-cycles. We conjecture that link-irregular tournaments exist if and only if n ≥ 6, providing explicit constructions for n ≤ 8 and computational verification for n ≤ 100. We derive lower bounds on the minimum degree and outdegree required for link-irregularity, establish that almost all link-irregular digraphs are nonplanar, and prove that any link-irregular orientable graph admits a link-irregular labeling. Additionally, we construct explicit examples of link-irregular digraphs with constant outdegree and regular tournaments.
In this paper, we follow standard terminology and notation in graph theory as presented in West’s textbook [7]. For a graph \(G\) with vertex set \(V(G)\) and edge set \(E(G)\), the number of vertices and edges in a graph \(G\) are denoted by \(n(G)\) and \(e(G)\), respectively. The degree of a vertex \(u \in V(G)\), \(d(u)\), is the number of edges connected to vertex \(u\). And \(D(G)\) is the set of degrees of the vertices of graph \(G\). A graph is irregular if no two vertices in the graph have the same degree. It is known that no such graph exists because there is no simple graph in which all vertex degrees are distinct. Ali, Chartrand, and Zhang [1] introduced the notions of the link of a vertex, link-regular graphs, and link-irregular graphs. The link \(L(v)\) of a vertex \(v\) in a graph \(G\) is defined as the subgraph induced by the neighborhood of \(v\); that is, \(L(v) = G[N(v)]\). A graph \(G\) is link-irregular if every pair of distinct vertices has non-isomorphic links; that is, \(L(u) \ncong L(v)\) for all distinct \(u, v \in V(G)\).
Recently, Bastien and Khormali in [4] obtained the results: there are no bipartite or regular link-irregular graphs for small orders, and only finitely many link-irregular graphs are planar. Also, they disprove a conjecture that no regular link-irregular graphs exist, through explicit and probabilistic constructions.
Also, Bastien and Khormali in [3] introduced link-irregular labelings for undirected graphs by assigning positive integer labels to edges, effectively modeling loopless multigraphs while working within the framework of simple graphs. This allowed them to distinguish each vertex by the labeled subgraph induced by its neighbors. They characterized the existence of such labelings, defined the link-irregular labeling number, and showed that while families like bipartite graphs and cycles do not admit such labelings, complete and wheel graphs do. They also proved that any labeling number can be realized by some graph.
In this paper, we extend the study to directed graphs, examining how directionality impacts link-irregularity. The directed link \(L_D(v)\) of a vertex \(v\) in a digraph \(D\) is defined as the subgraph induced by the neighborhood of \(v\); that is, \(L_D(v) = D[N^+(v)\cup N^-(v)]\) where \(N^+(v)\) denotes the set of vertices with arcs from \(v\) (out-neighbors), and \(N^-(v)\) denotes the set of vertices with arcs to \(v\) (in-neighbors). Note that when \(D\) is understood to be a digraph, we will simply write \(L(v)\) for the directed link. A digraph \(D\) is link-irregular if every pair of distinct vertices has non-isomorphic directed links; that is, \(L_D(u) \ncong L_D(v)\) for all distinct \(u, v \in V(G)\).
Throughout this paper, all digraphs will be orientations of simple graphs.
In this paper, we shall use the following definitions.
Definition 2.1. Let \(D\) be a digraph. Then the underlying graph of \(D\), denoted \(U(D)\) is the graph obtained by replacing all the directed edges of \(D\) with undirected edges.
Definition 2.2. Let \(D\) be a digraph and \(v\) a vertex of \(D\). Let \(N\) consist of all vertices of \(D\) that are neighbors of \(v\) in \(U(D)\). We define the directed link \(L_D(v)\) of \(v\) to be the subdigraph of \(D\) induced by the set \(N\). When there is no risk of confusion, we may also denote the directed link by \(L(v)\).
We say that \(D\) is link-irregular if for two distinct vertices \(u, v\) of \(D\), \(L(u)\ncong L(v)\).
Now we will use the following result from [5] to prove a simple condition that all link-irregular digraphs must satisfy.
Proposition 2.3. [5]If \(G\) is a graph, then there exist two vertices \(u, v \in V(G)\) such that \(d(u) = d(v)\).
We are now ready to state the following observation.
Observation 2.4. If a digraph \(D\) is link-irregular, then \(U(D)\) contains a 3-cycle.
Proof. Suppose \(D\) is a link-irregular digraph. By Proposition 2.3, \(D\) has two vertices with the same degree. Call this common degree \(d\). Since \(D\) is link-irregular, these cannot both have \(\overline{K}_d\) as their links because this would imply their links are isomorphic. Hence \(L(u)\) or \(L(v)\) has an edge, so this makes a triangle in the underlying graph. This completes the proof. ◻
We now use this condition to examine a few examples of what cannot be a link-irregular digraph.
Observation 2.5. If \(U(D)\) is a tree, bipartite graph, hypercube, or wheel graph, then \(D\) is not link-irregular.
Proof. If \(U(D)\) is a tree, bipartite graph, or hypercube, then \(U(D)\) contains no 3-cycle, so \(D\) cannot be link-irregular.
Now we consider the case where \(U(D)\) is a wheel. We first consider the smallest wheel, \(W_3\), which consists of a triangle (3-cycle) and a central vertex connected to each vertex of the cycle. In this case, the underlying links in \(U(D)\) of the three cycle vertices are each isomorphic to the path \(P_3\). Each pair of these links shares a common edge, and any assignment of directions to the arcs will necessarily result in at least two directed links in \(D\) being isomorphic. Therefore, no orientation of \(W_3\) yields a link-irregular digraph.
Now consider \(W_4\), which contains a 4-cycle and a central hub vertex. In any orientation of \(W_4\), two non-adjacent cycle vertices will have the same directed link in \(D\). So the digraph cannot be link-irregular under any orientation.
More generally, for \(W_n\) with \(n \geq 5\), although the number of distinct links in increases, the number of possible orientations of links remains limited. Since each edge has only two possible directions, the number of distinct induced directed links is smaller than the number of vertices (see Figure 1). Furthermore, the structural symmetry of the wheel graph ensures that multiple vertices will have isomorphic neighborhoods and, hence, isomorphic directed links. Therefore, for any orientation of \(W_n\), there will exist at least two vertices with isomorphic directed links, and the digraph is not link-irregular. ◻
The following result is about the existence of link-irregular digraphs on a given number of vertices.
Theorem 2.6. There exists a link-irregular digraph \(D\) with \(|D| = n\) if and only if \(n \geq 5\).
Proof. If \(D\) has \(4\) or fewer vertices, we simply check all possible underlying graphs \(U(D)\) to verify that \(D\) cannot be link-irregular. If \(D\) has two vertices, these vertices both either have \(\overline{K_1}\) or \(K_1\) as their link. In either case, they both have the same link. If \(D\) has three vertices, there are either two vertices of degree \(0\), two vertices of degree \(1\), or three vertices of degree \(2\). In the first and second cases, these two vertices trivially have the same directed link. In the third case, at least two of these vertices must have the same link in \(U(D)\), and since no graph on \(2\) vertices has multiple distinct orientations, these vertices must have isomorphic links in \(D\). If \(D\) has four vertices, we see through observing all possible underlying graphs that are shown in Figure 2, each graph has two vertices of degree \(0\), two vertices of degree \(1\), two vertices of degree \(2\), or four vertices of degree \(3\). In the first three cases, two vertices have isomorphic links as before. In the third case, \(U(D)\) is isomorphic to \(K_4\). Since there are only two distinct orientations of \(K_3\) but there are four vertices with link \(K_3\), some two vertices must have the same link in \(D\). Hence \(D\) is not link-irregular.
Now we show that there exists a link-irregular digraph on \(n\) vertices for \(n \geq 5\). If \(n=5\), the link irregular digraphs on 5 vertices are shown in Figure 3. If \(n \geq 6\), then we use the result from [2] that says that there is a link-irregular graph on \(n\) vertices for \(n \geq 6\). It is evident that any orientation of a link-irregular graph is a link-irregular digraph, so this proves our result. ◻
In [2], Ali, Chartrand, and Zhang claimed that there exists a unique link-irregular graph on a minimum number of vertices. That is, they stated that there is only one link-irregular graph on \(6\) vertices. This might lead the reader to ask uniqueness questions regarding link-irregular digraphs. In particular, the reader might ask whether there is any number \(n\) such that there is only one link-irregular digraph on \(n\) vertices. It turns out that there is no such number \(n\). We state this in our observation.
Observation 2.7. For any number \(n=1,2,3 \cdots\), there is either no link-irregular digraph on \(n\) vertices, or there is more than one link-irregular digraph on \(n\) vertices.
Proof. The result is clear for \(n < 5\) by the previous theorem. Suppose \(n = 5\). Then the two following digraphs (which happen to be non-isomorphic orientations of the same underlying graph) are distinct link-irregular digraphs on \(n\) vertices.
Suppose that \(n > 5\). Then by [1], there exists a link-irregular graph on \(n\) vertices. Since any automorphism of a digraph \(D\) induces an automorphism of \(U(D)\) and a link-irregular graph has no non-trivial automorphisms, no two orientations of a link-irregular graph are isomorphic. Since, by [4], any link-irregular graph on \(n\) vertices has at least \(2n-5 > 0\) edges, we have at least \(2^{2n-5} > 1\) distinct link-irregular digraphs on \(n\) vertices. ◻
Next, we will adapt a result from [4] to obtain an analogous result on edge bounds and planarity for link-irregular digraphs.
Theorem 2.8. Let \(f(n)\) denote the minimum number of edges in a link-irregular digraph on \(n\) vertices. Then \(f(n)=\Omega(n\sqrt{\log n})\).
Proof. This proof follows almost exactly as the analogous proof from [4]. An upper bound on the number of isomorphism classes of simple graphs on \(h\) vertices is \(2^{\binom{h}{2}}\). Since there are two possible orientations for each edge, we have an upper bound of \((2^{\binom{h}{2}})^2 = 2^{2 \binom{h}{2}}\) isomorphism classes of digraphs on \(h\) vertices. Given a number \(n\) of vertices, we may pick \(k\) such that \(2^{2 \binom{k}{2}} \leq n < 2^{2 \binom{k+1}{2}}\). For every value \(d\) such that \(1 \leq d < k\), a link-irregular graph on \(n\) vertices has at most \(2^{2\binom{d}{2}}\) vertices of degree \(d\) since otherwise two links must be isomorphic. Such a graph also has at least \(n – \sum\limits_{d=1}^{k-1} 2^{2\binom{d}{2}}\) vertices of degree at least \(k\). We have \[\sum d\left(v\right) \geq \sum\limits_{d = 1}^{k-1}d2^{2\binom{d}{2}} + k\left(n – \sum\limits_{d=1}^{k-1} 2^{2\binom{d}{2}}\right) = kn – \sum\limits_{d = 1}^{k-1}\left(k-d\right)2^{2\binom{d}{2}}.\]
Since \(2^{2\binom{k}{2}} \leq n < 2^{2\binom{k+1}{2}}\), \(k^2-k \leq \log n < k^2+k\). Hence, as \(n \rightarrow \infty\), \(k \rightarrow \sqrt{\log n}\). In addition, we have \[\sum\limits_{d = 1}^{k-1}\left(k-d\right)2^{2\binom{d}{2}} < k\sum\limits_{d = 1}^{k-1}2^{2\binom{d}{2}} < k\sum\limits_{i = 1}^{2\binom{k-1}{2}} 2^i = k\left(\frac{1-2^{2\binom{k-1}{2}}}{1-2}\right) = k\left(2^{2\binom{k-1}{2}} – 1\right).\]
Since \(n \geq 2^{2\binom{k}{2}}\), the term \(nk\) dominates \(k\left(2^{2\binom{k-1}{2}} – 1\right)\) and therefore dominates the term \(\sum\limits_{d = 1}^{k-1}\left(k-d\right)2^{2\binom{d}{2}}\). Combining this with the first inequality and the degree-sum formula, we obtain \(f\left(n\right) = \Omega\left(\frac{n\sqrt{\log n}}{2}\right) = \Omega\left(n\sqrt{\log n}\right)\). ◻
We note that in the term \(d=1\) in the sums, we assume the convention of defining \(\binom{d}{2} = 0\) for \(d < 2\).
We observe that this implies that almost all link-irregular digraphs are nonplanar (that is, their underlying graph is nonplanar). For, by this result, there exists some natural number \(N\) such that for \(n \geq N\), any link irregular digraph on \(n\) vertices has more than \(3n-6\) edges. We have this since \(n\sqrt{\log n}\) grows at a faster rate than any linear function. By [7], any graph on \(n\) vertices with more than \(3n-6\) edges is nonplanar. Hence we have the following.
Theorem 2.9. All but finitely many link-irregular digraphs are nonplanar.
We now establish lower bounds on the degree and outdegree that must exist in any link-irregular digraph, which provides the necessary conditions for link-irregularity.
Theorem 2.10. Any link irregular digraph must have:
A vertex \(u\) such that \(d(u) \geq h – \sum\limits_{d=1}^{h-1}\frac{h-d}{n}2^{2\binom{d}{2}}\), and
A vertex \(w\) such that \(d^+(w) \geq \frac{1}{2}\left(h – \sum\limits_{d=1}^{h-1}\frac{h-d}{n}2^{2\binom{d}{2}}\right)\).
where \(h = \left\lfloor \frac{1+\sqrt{1+4\log{n}}}{2}\right\rfloor\)
Proof. We saw in Theorem 2.8 that \[\sum d(v) \geq hn – \sum\limits_{d = 1}^{h-1}(h-d)2^{2\binom{d}{2}}\] where \(h\) is the maximum integer satisfying \(2^{2\binom{h}{2}} \leq n\), \(n\) the number of vertices in our digraph. Taking the log of both sides of this inequality, we obtain \(2\binom{h}{2} = h^2-h \leq \log{n}\) which is equivalent to \(h^2-h-\log{n} \leq 0\). Setting the left-hand side of this inequality equal to zero, we obtain \(h = \frac{1 \pm \sqrt{1 + 4\log{n}}}{2}\). Since we wish to maximize \(h\), and \(h\) must be an integer, we have \[h = \left\lfloor \frac{1+\sqrt{1+4\log{n}}}{2}\right\rfloor\].
Using the first inequality we took from Theorem 2.8, we divide through by \(n\) to obtain \[\frac{1}{n}\sum d(v) \geq h – \sum\limits_{d = 1}^{h-1}\frac{h-d}{n}2^{2\binom{d}{2}}\].
By the pigeonhole principle, we have the first statement of our theorem. To obtain the second statement of our theorem, we observe that \(\sum d^+(v) = \frac{1}{2}\sum d(v)\). Then, dividing through our earlier equation by two, we obtain \[\frac{1}{n}\sum d^+(v) = \frac{1}{2n}\sum d(v) \geq \frac{1}{2}\left(h – \sum\limits_{d = 1}^{h-1}\frac{h-d}{n}2^{2\binom{d}{2}}\right).\]
As before, by the pigeonhole principle, we have the second statement of our theorem. ◻
An immediate consequence of this result is the following corollary.
Corollary 2.11. Any digraph in which:
All vertices have a degree less than \(h – \sum\limits_{d=1}^{h-1}\frac{h-d}{n}2^{2\binom{d}{2}}\), or
All vertices have an outdegree less than \(\frac{1}{2}\left(h – \sum\limits_{d=1}^{h-1}\frac{h-d}{n}2^{2\binom{d}{2}}\right)\)
is not link-irregular.
Then in any link-irregular digraph with constant outdegree, all vertices must have an outdegree greater than or equal to \(\frac{1}{2}\left(h – \sum\limits_{d=1}^{h-1}\frac{h-d}{n}2^{2\binom{d}{2}}\right)\). That is, a link-irregular digraph on \(n\) vertices with constant outdegree \(k\) must satisfy \(k \geq \frac{1}{2}\left(h – \sum\limits_{d=1}^{h-1}\frac{h-d}{n}2^{2\binom{d}{2}}\right)\) where \(h = \left\lfloor \frac{1+\sqrt{1+4\log{n}}}{2}\right\rfloor\).
We now investigate the connection between link-irregular orientable graphs and link-irregular labeling. We introduce two new definitions.
Definition 2.12. [3] Suppose \(G\) is a simple graph. \(G\) is said to be link-irregular labelable if there exists an edge labeling of \(G\) such that given two vertices \(u,v\) of \(G\), there exists no isomorphism of the (undirected) links \(L(u)\) and \(L(v)\) that preserves the edge-labeling.
Definition 2.13. A simple graph \(G\) is said to be link-irregular orientable if \(G=U(D)\) for some link-irregular digraph \(D\).
To proceed, we recall a result from [3].
Observation 2.14. [3] Let \(G\) be a simple graph. Then \(G\) has a link-irregular labeling if and only if given any distinct \(x, y \in V(G)\), either \(L(x) \not\cong L(y)\), or \(E(L(x)) \neq E(L(y))\).
We are now ready to state our theorem.
Theorem 2.15. Suppose \(G\) is a link-irregular orientable graph. Then \(G\) is link-irregular labelable.
Proof. If \(L(u) \not\cong L(v)\) for any distinct vertices \(u, v \in V(G)\), then the result follows immediately since the underlying graph is already link-irregular. Suppose now that \(L(u) \cong L(v)\) in \(G\) for distinct vertices \(u, v \in V(G)\). If \(E(L(u)) = E(L(v))\), then we must also have \(E(L_D(u)) = E(L_D(v))\) for any orientation \(D\) of \(G\). Consequently, \(L_D(u) \cong L_D(v)\) for every orientation \(D\), and so \(G\) is not link-irregular orientable, contrary to our hypothesis. Therefore, we must have \(E(L(u)) \neq E(L(v))\), and hence, by Observation 2.14, \(G\) is link-irregular labelable. ◻
Following this result, the natural question is whether the converse is true. It turns out that the converse is not true.
Observation 2.16. The following graph is link-irregular 2-labelable, but not link-irregular orientable.
Proof. To prove that this graph has a link-irregular 2-labeling, we provide one.
To see that this graph has no link-irregular orientation, we notice that two vertices have \(K_2\) as a link. Since \(K_2\) only has one orientation up to isomorphism, there is no possible link-irregular orientation of this graph. ◻
We now turn our attention to special classes of digraphs with regularity constraints. In particular, we investigate whether link-irregularity can coexist with strong connectivity and balanced degree properties. To formalize this discussion, we first recall the relevant definitions.
Definition 3.1.[7] [Strongly Connected Digraph] A directed graph (digraph) \(D = (V, A)\) is said to be strongly connected if for every pair of vertices \(u, v \in V\), there exists a directed path from \(u\) to \(v\) and a directed path from \(v\) to \(u\).
Definition 3.2.[7] [Eulerian Digraph] A digraph \(D = (V, A)\) is called Eulerian if it is strongly connected and for every vertex \(v \in V\), the in-degree equals the out-degree; that is, \(d^+(v) = d^-(v)\).
The following observation follows from the preceding definitions.
Observation 3.3. For all integers \(n \geq 3\) and \(1 \leq k \leq n – 1\), there exist Eulerian digraphs on \(n\) vertices with outdegree \(k\) that are not link-irregular.
Proof. Fix \(n \geq 3\) and let \(k \in \{1, 2, \dots, n-1\}\). Define the digraph \(D = (V, A)\) as follows: \[V = \{v_0, v_1, \dots, v_{n-1}\},\] \[A = \{ v_i \to v_{(i + j) \bmod n} \mid 1 \leq j \leq k,\ 0 \leq i \leq n – 1 \}.\]
In this construction, each vertex has outdegree \(k\), sending arcs to the next \(k\) vertices cyclically. Also, each vertex also has indegree \(k\), since it receives arcs from the \(k\) preceding vertices modulo \(n\). The digraph is strongly connected because the steps \(\{1, 2, \dots, k\}\) generate the full group \(\mathbb{Z}_n\) (especially when \(\gcd(k, n) = 1\)), and in general the structure ensures reachability via directed paths. Thus, \(D\) is Eulerian. However, due to the rotational symmetry of the construction, all vertices have isomorphic directed links. Specifically, for each vertex \(v_i\), the link \(L_D(v_i)\) is induced by the same relative configuration of neighbors. Therefore, \(D\) is not link-irregular. ◻
We now present several observations on the existence of link-irregular digraphs with specific properties.
Observation 3.4. There exists a link-irregular digraph on \(6\) vertices in which all vertices have the same outdegree \(2\).
Proof. Consider the digraph \(D_6\) on vertex set \(V = \{0, 1, 2, 3, 4, 5\}\) with edge set as shown in Figure 5. Each vertex has outdegree exactly \(2\), making this a 2-out-regular digraph. Direct computation shows that all vertices have distinct link-degree sequences, confirming that \(D_6\) is link-irregular. ◻
We next consider link-irregular digraphs with both constant in-degree and constant out-degree.
Observation 3.5. There exists a link-irregular digraph on \(9\) vertices in which all vertices have the same outdegree and indegree \(4\). Further, this graph is a tournament.
Proof. We construct an explicit example of such a digraph. Consider the tournament \(D_9\) on vertex set \(V = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}\) with edge set as depicted in Figure 6. By construction, each vertex has outdegree 4 and indegree 4, making this a regular tournament. To verify link-irregularity, we compute the link-outdegree sequence. A direct calculation shows that no two vertices share the same multiset of neighbor degrees, confirming that \(D_9\) is link-irregular. Therefore, there exists a link-irregular regular tournament on 9 vertices. ◻
The edge sets for the digraphs in Figures 5
and 6 are available
in Digraph_examples_edg-
esets.txt in the repository1.
This leads us to ask when a link-irregular tournament exists on \(n\) vertices. We address this here.
Observation 3.6. There exists a link-irregular tournament on \(n=6,7,8\) vertices, but there exists no link-irregular tournament on \(n \leq 5\) vertices.
Proof. We first prove the second statement of this observation. By Theorem 2.6, we only have to show that there does not exist a link-irregular tournament on \(5\) vertices. This is the case. For if a link-irregular tournament on 5 vertices existed, the link of each vertex would be an orientation of \(K_4\), but there are only four distinct orientations of \(K_4\) which are shown in Figure 7. Therefore, since there are \(5\) vertices, some two vertices must have isomorphic links.
Now we show that there does indeed exist a link-irregular tournament on \(n\) vertices for \(6\leq n \leq 8\). We claim the tournament on \(6\) vertices in Figure 8 is a link-irregular tournament.
We first note the in-degree sets of the link each vertex in this graph:
| \(L(1): \{1,1,1,3,4\}\) | \(L(4): \{0,2,2,3,3\}\) |
| \(L(2): \{1,1,2,2,4\}\) | \(L(5): \{1,1,2,3,3\}\) |
| \(L(3): \{1,1,2,3,3\}\) | \(L(6): \{1,2,2,2,3\}\) |
The only two vertices that have the same in-degree sequence are \(L(3)\) and \(L(5)\). We look closer at these two links. Each of these links has a vertex of in-degree \(2\). We count the number of directed \(3\)-cycles that contain this vertex of degree \(2\). In \(L(3)\), we count three such cycles while we only observe one in \(L(5)\). So these links are not isomorphic. We have proved that this tournament is link-irregular. Call this tournament \(D_6\).
To form the link-irregular tournament \(D_7\), we add a vertex \(w\) to \(D_6\) and add edges from this new vertex to each vertex of \(D_6\). It is immediate that if \(L(u) \cong L(v)\) in \(D_7\), then \(L(u)\cong L(v)\) in \(D_6\) as well. If \(L(u)\cong L(w)\) for some vertex \(u\) of \(D_6\), then since \(w\) is a vertex of out-degree \(5\) in \(L(u)\), there must be some vertex of out-degree \(5\) in \(L(w)\). But \(L(w) = D_6\), and \(D_6\) has no vertex of out-degree 5. Hence \(D_7\) is link-irregular.
To form the link-irregular tournament \(D_8\), we add a vertex \(z\) to \(D_7\) and add edges from each vertex of \(D_7\) to \(z\). As before, \(L(u) \ncong L(v)\) for \(u,v\) vertices in \(D_7\). If \(L(u) \cong L(z)\) then \(L(u)\) has a vertex of in-degree \(6\), hence \(L(z)=D_7\) does too. But \(D_7\) has no vertex of in-degree \(6\). Hence \(D_8\) is link-irregular. ◻
We had attempted to extend this construction to all values of \(n\). However, if we were to repeat this as a two-step process, then we would end up having two isomorphic links in \(D_9\). In particular, these would be the links of the vertex added to obtain \(D_9\) and the vertex added to obtain \(D_7\). When attempting to account for this and adjust our construction, it quickly became unruly and impossible to work with. We present the following conjecture alongside computational evidence for it in certain cases.
Conjecture 3.7. A link-irregular tournament exists on \(n\) vertices if and only if \(n\geq 6\).
We developed a computer program to search for link-irregular tournaments, employing a multi-strategy approach including random generation, hill-climbing with edge flips, and seeded extension from known examples. Link graph isomorphism is detected using invariant signatures (vertex/edge counts, degree sequences, and directed 3-cycle counts) for efficient filtering, followed by full isomorphism testing via the VF2 algorithm [6]. Algorithm 1 outlines our approach.
Using this algorithm, we heuristically computationally verified the following result via a non-exhaustive search. For each tested value of \(n\), the algorithm successfully found a link-irregular tournament within the prescribed attempt limits. The upper bound \(n = 100\) was chosen based on reasonable computational time; the algorithm can be extended to larger values with additional computing resources. Complete source code and detailed algorithmic specifications are available at https://github.com/omidkhormali/Link-irregular-Digraphs.
Observation 3.8. For \(n \leq 100\), Conjecture 3.7 holds.
Finally, in the following remark, we note a potential avenue of attack to prove this conjecture.
Remark 3.9. In [3], the
authors of this paper introduced the concept of a link-irregular
labeling. This idea can naturally be extended to digraphs by replacing
graph isomorphism in all definitions with digraph isomorphism. In this
paper, it is proven that there exists a link-irregular 2-labeling of
\(K_n\) if and only if \(n \geq 6\). Any orientation of such a
labeling is a link-irregular 2-labeled tournament.
Suppose that we have a link-irregular 2-labeled tournament. We would
like to show that if we change one edge label from its current label to
the other possible label, we can change the directions of the edges in
the tournament so that we still have a link-irregular 2-labeled
tournament. This has proven rather tricky and is the sticking point of
this idea for a proof. If, however, this can be proven, then the
conjecture follows immediately. We can change the edge labels and adjust
the edge orientations repeatedly until we obtain a monochromatic
link-irregular digraph. But then this is a link-irregular
tournament.
This research was supported by the UExplore Undergraduate Research Program at the University of Evansville.
No datasets were generated during this study. The Python code used for computational verification of Conjecture 6 is publicly available at https://github.com/omidkhormali/Link-irregular-Digraphs.
The authors declare that they have no conflict of interest.