1. Introduction
We use the standard notation. By an edge we mean an unoriented pair of vertices, and by an arc we mean an oriented pair of vertices. For a given graph G,
and
denote the set of its vertices and the set of its edges, respectively. For a digraph G, we write
for the set of its arcs. By an oriented graph we mean such a digraph that if
is an arc, then
is not. All graphs and digraphs in this paper are finite.
2. Motivation
Orientation of a graph G is called transitive if for every
,
, also
. This concept was studied by many authors in numerous papers, see the survey [1] for example. The concept of transitive orientation was generalized in several ways in [2] and [3] , [4] and [5] , and other papers.
A digraph is called k-transitive if every directed path of the length k has a shortcut joining the beginning and the end of this path. In other words, if
is a path in the digraph G, then
.
Note that our term “k-transitive” coresponds to “
-transitive” in [2] and [3] .
A k-transitive closure of an oriented graph
is an oriented graph
such that
(1) ![](//html.scirp.org/file/2-5300983x18.png)
(2) ![](//html.scirp.org/file/2-5300983x19.png)
(3)
is k-transitive.
(4) it has the minimal (by inclusion) set of arcs among all graphs with the above stated properties.
Observe that there are oriented graphs for which the k-transitive closure does not exist. For example in a cyclically oriented cycle
it is not possible to add arcs to fulfill the condition (3).
If the k-transitive closure does exist for some oriented graph, it is unique.
Note that this definition is a partial answer to the point (4) in ([2] , p. 41).
The aim of this paper is to describe k-transitive closures of directed paths.
3. Structure of the k-Transitive Closure of the Directed Path
Instead of
we write
to denote the k-transitive closure of an oriented path on n vertices. We label the vertices by natural numbers
and assume that
for
.
Although the graph
is oriented, some of the properties will be stated for simple graphs obtained by “forgetting” the orientation. We belive that it is clear from the context, but to be precise, for the unoriented case we write
.
In this paper by a degree sequence of a graph
we mean a sequence
. (In/out) degree sequence of a graph
is defined in a similiar way.
Observe that
is just the complete graph
, and
is the tournament on n vertices.
The starting point in a construction of the k-transitive closure of the path
is to add arcs
. Then we add arcs
, at the next stage arcs
, and so on. This construction shows that for every
,
is well defined.
The key observations are:
3.1 Fact. Adding one vertex to the path adds only arcs ending in this new vertex. In other words,
is an induced subgraph of
. □
3.2 Fact. In the graph
,
iff
for some
.
Proof. It follows directly from the construction described above that
![]()
To show the other inclusion we use the induction on n. First observe that for
all arcs are of the form
. Assume that all arcs in
have the length
for some
. To obtain a k-shortcut in
we need k arcs, each of them of length
,
. So
. □
In Figure 1 we present the graph
as an example.
4. Some Properties
From the observations mentioned above, we conclude several properties of graphs
and
.
4.1 Fact. For
,
. So for
, the graph
is just the path
. □
We can observe the following block structure in indegree/outdegree sequences of graphs
:
![]()
Figure 1. The graph
. All arcs ending in the last vertex are drawn with thick lines.
4.2 Theorem. Let
for some
and
. In the oriented graph
the indegree sequence is built from uniform “blocks” of length
and has the form
![]()
Similarly, the outdegree sequence is built from uniform “blocks” of length
and has the form
![]()
Proof. The proof follows from Facts 3.2 and 3.1. We prove the part concerning the indegree sequence. First note that the indegree of the first vertex is 0. For the next
vertices there is no arcs ending in them other
than the arcs in the initial path, so their indegree is 1. First vertex of indegree 2 is the
-th vertex. First vertex of indegree 3 is the 2k-th vertex, and first vertex of indegree j is the
-th vertex.
The proof for the outdegree sequence is similiar; we just start from the last vertex. □
4.3 Corollary. The graph
is
-regular for every
.
Proof. This is a consequence of Theorem 4.2; just observe that summing up the indegree and outdegree sequences gives the constant sequence
. □
4.4 Corollary. For every
, and for every
, all vertices of the graph
has degree
or
. Morover, if we put
and
, the degree sequence is built from “blocks” of the form
![]()
repeated to get the sequence of the length
. Note that the last “block” has the length
.
Proof. This is another consequence of Theorem 4.2. □
4.5 Corollary. For every
, and for every
, in the graph
there are
vertices of degree
and
vertices of degree
. □
As an example, below are the degree sequences for 5-transitive closures of the paths on 10, 11, 12, 13 and 14 vertices:
• for
:
;
,
and
, by Corollary 4.3 this graph is 2 + 1 = 3 regular;
• for
:
;
,
and
, by Corollary 4.4 this sequence is built from repeated blocks
;
• for
:
;
,
and
, by Corollary 4.4 this sequence is built from repeated blocks
;
• for
:
;
,
and
, by Corollary 4.4 this sequence is built from repeated blocks
;
• for
:
;
,
and
, by Corollary 4.3 this graph is 3 + 1 = 4 regular.
Recall that by degree of a vertex v in a digraph we mean a pair
.
For oriented graphs
we can observe the following:
4.6 Corollary. Every constant subsequence in the degree sequence of the non regular graph
is also the constant subsequence in the degree sequence of the oriented graph
. □
For example, the degree sequence for
is
, and the degree sequence for
is
.
Recall that an oriented graph G is irregular if for every two vertices
,
, their degrees are different.
Straightforward consequence of Corollary 4.6 is that graphs
for
are not irregular. The natural question is: are the graphs
irregular? The answer is:
4.7 Theorem. Oriented graphs
are irregular iff n is odd.
Proof. By Theorem 4.2, pairs of vertices
for
have the same indegree. Because for the even n the graph
is regular, so
is not irregular if
is even.
Also by Theorem 4.2,
for
. By Corollary 4.4, for the odd n the degree sequence of the graph
is of the form
. So for n odd, if for some two vertices their total degrees are equal then its indegrees are different. Hence
is irregular if n is odd. □
Recall that the tournament
is irregular for any n.
5. Density
By density of the graph G,
, we mean ratio “number of edges in the graph G” / “number of edges in complete graph
”; in symbols
.
Recall then for every even n, a graph
is
-regular. We have
edges. So for even n,
.
For every odd n, in a graph
there are
vertices of degree
and
vertices of degree
. We have
edges. So for odd n,
.
Observe that in both cases the density is bigger then 1/2 and
![]()
We have the following:
5.1 Theorem. For
,
![]()
Proof. By Corollary 4.5,
![]()
By standard calculation we get
![]()
Recall that
, where k and m are fixed, so when
, then also
. So
□
Obviously, for
,
.
6. Open Problems
The main open problem concerning k-transitive closures in general, is to state what properties of an oriented graph G guarantee the existence of
.
There are also some other special classes of oriented graphs, such as cycles (with different orientations) and trees, for which there is a chance to obtain interested properties for their k-transitive closures.
Acknowledgements
We acknowledge the support by the UJK grant No. 612439.
Some of the results contained in this paper were presented at the 5th Polish Combinatorial Conference, Będlewo, September 22-26, 2014. The author wants to express his thanks to Professor Zsolt Tuza for pointing to valuable references.