# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## PROBLEMS ON FULLY IRREGULAR DIGRAPHS

Zdzisław Skupień

Faculty of Applied Mathematics
University of Mining and Metallurgy AGH
al. Mickiewicza 30, 30-059 Kraków, Poland
e-mail: skupien@uci.agh.edu.pl

A simple graph with more than one vertex is well-known 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 2-cycles C2).

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 digraphs-introduced by the present author in 1995-is 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 = {v1,…, vn} 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 ui and wi, 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 (wj, ui) 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 u0 and from w0 to V, and possibly arcs (v,ui) and/or (wi,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,u0) and (w0,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. ) 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 o-deficit of D. Clearly, f(D) ≤ f′(D). Let f(n) (and f′(n)) be the largest irregularity deficit (resp. largest irregularity o-deficit ) among n-vertex digraphs.

Corollary 3 The irregularity o-deficit among n-vertex digraphs is bounded by 2⎡√n  ⎤. Thus

 f(n) ≤ f′(n) ≤ 2⎡√n  ⎤.

Problem 1 (Problem 1'). Characterize n-vertex digraphs D with the largest possible irregularity deficit f(D) (o-deficit 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. ). If D is an r-diregular 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. ). If D is an r-diregular 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

  Z. Dziechcińska-Halamoda, Z. Majcher, J. Michael, and Z. Skupień, Sets of degree pairs in the extremum fully irregular digraphs, in preparation.  J. Górska, Z. Skupień, Z. Majcher, and J. Michael, A smallest fully irregular oriented graph containing a given diregular one, submitted.  J. Górska and Z. Skupień, A smallest fully irregular digraph containing a given diregular one, in preparation.  F. Harary and E.M. Palmer, Graphical Enumeration (Academic Press, New York, 1973).  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.