Discussiones
Mathematicae Graph Theory 19(2) (1999) 253255
DOI: 10.7151/dmgt.1102
PROBLEMS ON FULLY IRREGULAR DIGRAPHS
Zdzisław Skupień
Faculty of Applied Mathematics
University of Mining and Metallurgy AGH
al. Mickiewicza 30, 30059 Kraków, Poland
email: skupien@uci.agh.edu.pl
A simple graph with more than one vertex is wellknown to have two vertices of the same degree. This amounts to saying that no simple nontrivial graph can be fully irregular. Recall that directing each edge of a simple graph results in an oriented graph (which is a digraph without 2cycles C_{2}→).
A digraph D is called fully irregular if distinct vertices of D have distinct degree pairs. The degree pair of a vertex is the outdegree followed by the indegree of the vertex. The notion of fully irregular digraphsintroduced by the present author in 1995is investigated in [1,2,3,5]. Some results on fully irregular digraphs were presented at international conferences held in Poland at Lubiatów '96, Gronów '97, '98, and at Kazimierz Dolny '97.
Theorem 1 Let D be a digraph of order n. There exists an injection D→ D′ which associates with D a fully irregular digraph D′ of order n+2⎡√n ⎤ such that D is an induced subdigraph of D′ and such that deleting all arcs of D from D′ results in an oriented graph.
Proof. Let V = {v_{1},…, v_{n}} be the vertex set of D. Let t = ⎡√n ⎤1.Consider two disjoint linearly ordered sets U and W which comprise altogether 2(t+1) new vertices respectively u_{i} and w_{i}, which are ordered by increasing subscripts i, i = 0,1, …,t. Let B be the bipartite digraph whose vertex set is U∪W and all arcs are of the form (w_{j}, u_{i}) for each i ∈ {0,1,…,t−j} where j = 0,1,…,t. Let D′ be a digraph of order n+2t+2 which includes disjoint digraphs D and B, all arcs both from V to u_{0} and from w_{0} to V, and possibly arcs (v,u_{i}) and/or (w_{i},v) where v ∈ V and, moreover, the neighbours of any such v both in U and W make up precisely initial segments of U and W, respectively. Hence the outdegrees and indegrees of vertices from U and W, respectively, are all zero. Therefore the two obligatory arcs (v,u_{0}) and (w_{0},v) for each vertex v of D enable us to identify D as the subdigraph of D′ induced by all vertices whose outdegrees and indegrees are all positive.
For any vertex v of D the optional arcs (possibly none) from v to a segment of U can be chosen in t+1 ways. The same is the number of choices for remaining optional arcs from a segment of W to v. Thus the degree pair in D′ of each vertex v can be any of some (t+1)^{2} ( ≥ n) points in the plane integral lattice. Therefore distinct degree pairs in D′ for all n vertices of D can be designed and realized. The construction associates mutually distinct degree pairs with all remaining vertices, too. Therefore a required injection exists.
Corollary 2 There are at least as many fully irregular digraphs (oriented graphs) of order n+2⎡√n ⎤ as there are digraphs (oriented graphs) of order n.
It seems likely that fully irregular digraphs can contribute to finding a constructive proof (which is lacking) of the fact (cf. [4]) that almost all digraphs have trivial automorphism group. Given a digraph D on n vertices, let f(D) (and f′(D)) be the smallest integer t such that a fully irregular digraph D~ on n+t vertices includes D as an induced subdigraph (and such that deleting the arc set A(D) of D from D~ results in an oriented graph). Name f(D) and f′(D) respectively the irregularity deficit and irregularity odeficit of D. Clearly, f(D) ≤ f′(D). Let f(n) (and f′(n)) be the largest irregularity deficit (resp. largest irregularity odeficit ) among nvertex digraphs.
Corollary 3 The irregularity odeficit among nvertex digraphs is bounded by 2⎡√n ⎤. Thus

Problem 1 (Problem 1'). Characterize nvertex digraphs D with the largest possible irregularity deficit f(D) (odeficit f′(D)), i.e., with f(D) = f(n) (resp. f′(D) = f′(n)).
Given a nonnegative integer r, a digraph D is called r diregular if degree pairs in D are all (r,r).
Theorem 4 (Górska et al. [2]). If D is an rdiregular oriented graph on n vertices then f′(D) = ⎣√[2n]−[1/2]⎦ for n ≥ 1 unless n = 3, r = 1, and then f′(D) = 2.
Theorem 5 (Górska et al. [3]). If D is an rdiregular digraph on n vertices then f(D) = ⎣√[(n−1)]⎦( = ⎡√n ⎤−1) for n ≥ 1 unless n = 4, r ∈ {1,2}, and then f(D) = 2.
References
[1]  Z. DziechcińskaHalamoda, Z. Majcher, J. Michael, and Z. Skupień, Sets of degree pairs in the extremum fully irregular digraphs, in preparation. 
[2]  J. Górska, Z. Skupień, Z. Majcher, and J. Michael, A smallest fully irregular oriented graph containing a given diregular one, submitted. 
[3]  J. Górska and Z. Skupień, A smallest fully irregular digraph containing a given diregular one, in preparation. 
[4]  F. Harary and E.M. Palmer, Graphical Enumeration (Academic Press, New York, 1973). 
[5]  Z. Majcher, J. Michael, J. Górska, and Z. Skupień, The minimum size of fully irregular oriented graphs, in: Proc. Kazimierz Dolny '97 Conf., Discrete Math., to appear. 
Received 8 April 1999
Revised 14 September 1999