Iterations of eccentric digraphs

Mirka Miller School of Electrical Engineering and Computer Science The University of Newcastle, NSW 2308, Australia

            e-mail: mirka@cs.newcastle.edu.au

Joan Gimbert Departament de Matematica Universitat de Lleida, 25001 Lleida, Spain

                e-mail: joangim@eup.udl.es

Frank Ruskey Department of Computer Science

University of Victoria, Victoria, B.C. V8W 3P6, Canada

                e-mail: fruskey@cs.uvic.ca

Joseph Ryan Newcastle Graduate School of Business The University of Newcastle, NSW 2308, Australia

            e-mail: joe.ryan@newcastle.edu.au

Abstract

The eccentricity e(u) of vertex u is the maximum distance of u to any other vertex of G. A vertex v is an eccentric vertex of vertex u if the distance from u to v is equal to e(u). The eccentric digraph ED(G) of a digraph G is the digraph that has the same vertex set as G and the arc set defined by: there is an arc from u to v if and only if v is an eccentric vertex of u. In this paper we consider the behaviour of an iterated sequence of eccentric graphs or digraphs of a graph or a digraph. The paper concludes with several open problems.

Keywords: Eccentricity, eccentric vertex, distance, eccentric graph, eccentric digraph.

1 Introduction and definitions

The study of distance properties of graphs is a classic area of graph theory; see, for example, the books of Buckley and Harary [5] and Brouwer, Cohen, Neumaier [3]. We study here an iterated version of a distance dependent mapping introduced by Buckley [4] and refined by others, including Boland and Miller [1]. The mapping is very simple but leads naturally to rather subtle questions. The questions posed are of the type studied by extremal graph theorists, but even they may consider our problems rather extreme!

A directed graph G = G(V, E) consists of a vertex set V (G) and an arc set E(G). For the purposes of this paper, a graph is a digraph for which (u, v) ∈ E implies (v, u) ∈ E. The least number of arcs in a directed path from u to v is the distance from u to v, denoted d(u, v). If there is no directed path from u to v in G then we define d(u, v) = ∞. The eccentricity, e(u), of u is the maximum distance from u to any other vertex in G. The radius is the minimum eccentricity of the vertices in G; the diameter is the maximum eccentricity of the vertices in G. Vertex v is an eccentric vertex of u if d(u, v) = e(u). Note that if a vertex has out-degree zero, that vertex has all the other vertices of the given digraph as its eccentric vertices.

The eccentric digraph of a digraph G, denoted ED(G), is the digraph on the same vertex set as G, but with an arc from vertex u to vertex v in ED(G) if and only if v is an eccentric vertex of u. The eccentric digraph of a graph was introduced by Buckley [4] and Boland and Miller [1] introduced the concept of the eccentric digraph of a digraph. An example of a graph and its eccentric digraph is given in Figure 1. Note that arcs of graphs are drawn not as a pair of directed edges with arrows, but in the usual form.

Figure 1: A graph and its eccentric digraph.

Given a positive integer k ≥ 2, the k^{th} iterated eccentric digraph of G is written as ED^{k}(G) = ED(ED^{k−1}(G)) where ED^{0}(G) = G. Figure 2 illustrates these definitions showing digraph G and its iterated eccentric digraphs ED(G), ED^{2}(G), ED^{3}(G), and ED^{4}(G). Note that in this case ED^{5}(G) = ED^{3}(G).

Figure 2: An eccentric digraph iteration sequence. 3

An interesting line of investigation concerns the iterated sequence of eccentric digraphs. n For every digraph G there exist smallest integer numbers p > 0 and t ≥ 0 such that ED^{t}(G) = ED^{p+t}(G). For example, in Figure 2, t(G) = 3 and p(G) = 2. We call p the period of G and t the tail of G; these quantities are denoted p(G) and t(G) respectively. We say that a graph is periodic if it has no tail; i.e., if t(G) = 0. In the definitions just given, we assumed that the vertices of the graphs are labelled. It is also natural to consider the corresponding unlabelled version.

For every digraph G there exist smallest integer numbers p > 0 and t ≥ 0 such that ED^{t}(G) ≅ ED^{p+t}(G), where ≅ denotes graph isomorphism. We call p the iso-period of G and t the iso-tail of G; these quantities are denoted p′(G) and t′(G) respectively. We say that a graph is iso-periodic if it has no iso-tail; i.e., if t′(G) = 0. Clearly p′(G) | p(G).

2 Previous results and conjectures

The following observations, theorems, and open problems first appeared in [1] or [2].

Observation 2.1 If a digraph G is the union of k > 1 vertex disjoint strongly connected digraphs of orders n_{1}, n_{2}, …, n_{k}, for m > 0,

ED^{m}(G) = \{ \begin{matrix}K_{n_{1},n_{2},...,n_{k}} & if m odd \\ K_{n_{1}} ∪ K_{n_{2}} ∪ … ∪ K_{n_{k}} & if m even. \end{matrix}

Observation 2.2 The eccentric digraph of a directed cycle is a directed cycle, ED(\overrightarrow{C}_{n}) ≅ \overrightarrow{C}_{n}. However, note that the direction of the arcs in ED(\overrightarrow{C}_{n}) is opposite to the direction of the arcs in the given cycle \overrightarrow{C}_{n}.

Observation 2.3 A nontrivial eccentric digraph has no vertex of outdegree zero. However, the converse is not true: there exist digraphs with the out-degree of every vertex non-zero which are, nevertheless, not the eccentric digraphs of any graph or digraph. An example of such a digraph is the graph P_{4}, the path of four vertices.

It seems likely that a classification of all digraphs as to whether or not they are an eccentric digraph is not a trivial problem.

Question 2.1 Find necessary and sufficient conditions for a digraph to be an eccentric digraph.

The fact that there exist digraphs which are not eccentric digraphs of any graph or digraph leads to the question: “If a digraph G is not an eccentric digraph, can G be always embedded in an eccentric digraph?” This question was considered in [2]. The eccentric digraph appendage number of G is the minimum number of vertices that must be added to a digraph G so that there exists a digraph G′ which is the eccentric digraph of some digraph and G is an induced subgraph of G′.

Theorem 2.1 If G is not the eccentric digraph of some graph H, then the eccentric digraph appendage number of G equals one.

Question 2.2 Find the period and the tail of various classes of graphs and digraphs.

Observation 2.4 The only digraph G with p(G) = 1 and t(G) = 0 is the complete digraph K_{n}.

Observation 2.5 For p = 2, t = 0 examples include the complete multipartite digraph K_{n_{1},n_{2},...,n_{k}}, the disjoint union of complete digraphs K_{n_{1}} ∪ K_{n_{2}} ∪ … ∪ K_{n_{k}} and the directed cycle \overrightarrow{C}_{n}.

Question 2.3 Characterize periodic digraphs with period two.

Observation 2.6 For p = 2, t = 1 examples include the (disjoint) union of strongly connected digraphs H_{n_{1}} ∪ H_{n_{2}} ∪ … ∪ H_{n_{k}}, where at least one of them is not a complete digraph.

3 Examples, open problems, and conjectures

In this section we present some examples and new open problems and questions, all designed to stimulate further interest in the iterated eccentric mapping. Many examples of digraphs G with p(G) = 2 have been found. In fact, if you pick a digraph at random on a computer then it usually occurs that p(G) = 2 and you have to work quite hard to find one of larger period. This observation leads to our first conjecture.

Conjecture 3.1 In the standard model of n-vertex random digraphs where arcs are chosen at random with probability q, if 0 < q < 1, then

lim_{n→∞} P rob_{q}(p(G) = 2) = 1.

Here we present for the first time examples of eccentric digraph iteration cycles of length more than 2. The following three examples give eccentric digraph iteration cycles of lengths 4 and 8.

Figure 3: The Cayley graph with generators (01)(23)(4567) and (56)(78).

Example 3.1 Let R be the (undirected) cubic Cayley graph with the two generators (01)(23)(4567) and (56)(78). The directed version is shown in Figure 3. The graph R has 20 vertices and is periodic with p(R) = 4. However, the graphs ED^{k}(R) are all isomorphic to R and so p′(R) = 1.

Example 3.2 Let R be as in Example 1. The conjunction (or tensor product) G = G_{1} ∧ G_{2} of two digraphs G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) has V = V_{1} × V_{2} as its vertex set, and u = (u_{1}, u_{2}) is adjacent to v = (v_{1}, v_{2}) in G iff (u_{1}, v_{1}) ∈ E_{1} and (u_{2}, v_{2}) ∈ E_{2}. For this graph, p(R ∧ R) = 8.

Example 3.3 The smallest digraph G found so far with p′(G) > 2 has 10 vertices and iso-period 4. Such a digraph G is shown in Figure 4.

Example 3.4 Let C_{n} denote the cyclic graph of n vertices. Consider the odd cycles, C_{2m+1}. Figure 5 illustrates that p(C_{9}) = 3. Below we show a table of p(C_{2m+1}). This is sequence A003558 in Sloane’s Encyclopedia of Integer Sequences.

\begin{matrix}m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ p(C_{2m+1}) & 1 & 2 & 3 & 3 & 5 & 6 & 4 & 4 & 9 & 6 & 11 & 10 & 9 & 14 & 5 & 5 \end{matrix}

It is not difficult to determine that

p(C_{2m+1}) = min{k ≥ 1 | m(m + 1)^{k−1} = ±1 (mod 2m + 1)}.

In particular, if m = 2^{k}, then p(C_{2m+1}) = k + 1, showing that the period may take on any value. The numbers m for which m = p(C_{2m+1}) have been called the “Queneau numbers” (e.g. Sloane’s A054639). Note that if m is Figure 4: A digraph G with of order 10 such that p(G) = p′(G) = 4 and t(G) = t′(G) = 1.

0  G = ED^{3}(G) ED(G) ED(ED(G))

Figure 5: The graph C_{9} and its iterated eccentric digraphs. a Queneau number, then the sequence of iterated eccentric digraphs gives a Hamilton decomposition of K_{2m+1}. They also show that the following conjectured bound, if true, is tight for infinitely many values of n.

Conjecture 3.2 For any digraph G of n vertices

p(G) ≤ \frac{n − 1}{2}.

Conjecture 3.3 We have observed, but not proven, that

p(C_{2m+1} × C_{2m+1}) = p(C_{2m+1}) + p(C_{2m+1}),

where × denotes the usual Cartesian product of graphs.

Example 3.5 The 336 vertex cubic Cayley graph with the two generators (23)(45)(67) and (025)(146) leads to a period 4 sequence G_{0}, G_{1}, G_{2}, G_{4}, where G_{0} ≅ G_{2} is an 8-regular graph, and G_{1} ≅ G_{3} is 14-regular graph. Thus, for this example, p(G) = 4 and p′(G) = 2.

Observation 3.1 A digraph G of order n satisfies that p(G) = t(G) = 1 if and only if G has k ≥ 1 vertices with out-degree 0 and n − k vertices with out-degree n − 1.

Observation 3.2 Vertex transitive graphs are sometimes said to be symmetric. Clearly, the eccentric digraph of a symmetric digraph is a symmetric digraph. A little thought reveals that the symmetric digraph of a symmetric graph is a symmetric graph. Similarly, the eccentric digraph of a Cayley (di)graph also a Cayley (di)graph. The generators of ED(G) are the products of the generators along the longest paths in G.

Clearly ED induces a partition of the set of all graph (and on the set of all unlabelled graphs). Let ⟨G⟩ denote the equivalence class of (labelled) graphs induced by ED; and let [G] represent the corresponding unlabelled equivalence class.

What are the properties of that partition? In Figure 6 we show the partitions of labelled graphs (on the left) and unlabelled graphs (on the right) induced by ED for n = 3. Note that there are 2^{n(n−1)} = 64 graphs represented on the left and 16 on the right.

Question 3.1 Among all digraphs G on n vertices, what is the minimum size of ⟨G⟩? The maximum size? The average size? What about [G]?

Question 3.2 Let us say that a class is periodic if every graph in the class is periodic. For general n, identify some periodic classes. Can the periodic classes be characterized?

Figure 6: The equivalence classes induced by ED on the sets of unlabelled and labelled graphs for n = 3. The number enclosed in semi-circles are the number of classes of that form.

Question 3.3 Which unlabelled graphs are fixed points; i.e., such that ED(G) = G? For example, for n = 3 there are five such graphs. As observed earlier, for labelled graphs, only the complete graph is a fixed point.

Question 3.4 For every digraph G, is it true that t(G) = t′(G)?

4 Acknowledgements

The third author would like to thank Scott Effler for doing some computations of iterated eccentric digraphs.

References

[1] J. Boland and M. Miller, The eccentric digraph of a digraph, Proceedings of AWOCA’01, July 2001, pp.66–70.

[2] J. Boland, F. Buckley and M. Miller, Eccentric digraphs, Discrete Mathematics, to appear.

[3] A.E. Brouwer, A.M. Cohen, A. Neumaier, Distance Regular Graphs, Springer-Verlag, Berlin, 1989

[4] F. Buckley, The eccentric digraph of a graph, Congressus Numerantium, to appear.

[5] F. Buckley and F. Harary, Distance in graphs, Addison-Wesley, Redwood City, CA, 1990. Chapman and Hill.