DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(2) (1999) 253-255
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, 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. [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 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. [2]). 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. [3]). 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

[1] Z. Dziechcińska-Halamoda, 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