TO
IRREGULARITY STRENGTH OF DIGRAPHS
by
Jesse D. Gilbert
M.A., Western Michigan University, 2003
A thesis submitted to the
University of Colorado Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
2008
1
A } }
i
This thesis for the Doctor of Philosophy
degree by
Jesse D. Gilbert
has been approved
by
Gilbert, Jesse D. (Pli.D., Applied Mathematics)
Irregularity Strength of Digraphs
Thesis directed by Professor Michael Jacobson
ABSTRACT
An irregular digraph is a digraph whose vertex degree pairs are all distinct.
Irregular digraphs and irregular multidigraphs have a very nice property that
they have an errorcorrecting degree matrix. In order to add to the study of
irregular multidigraphs, we introduce the term irregularity strength of digraphs.
Define a pair of maps /, g where / is from the arc set of a digraph into the
positive integers and where g induces vertex weights on the vertices subject to
9(v) = ( JL f(uv))
vxÂ£A(D) uvÂ£A(D)
If all the degree weights induced by g are distinct across the vertex set of D. then
we say / is an irregular labeling of the digraph D and g is an irregular vertex
weighting of the digraph D. Let I(D) be the set of irregular labelings of D. If s
is the maximum value of /(e) for e E A(D), we say / is an irregular slabeling, g
an irregular sweighting if / and g satisfy the above conditions. The irregularity
strength of a digraph D is the minimum such s used for / E 1(D). We define
the irregularity strength s of a digraph D to
s(D) = min max /(e).
fl(D) eGA(D)
We give various techniques for determining digraph irregularity strength
and constructing irregular labelings of digraphs using the minimum possible
maximum value as a label. In particular, if we know that s is the irregularity
strength of D, then we write s(D) = s. An irregular labeling of a digraph
with the minimal number of labels is an irregular slabeling of D. That is, we
give techniques for irregular slabelings of tournaments, some orientations of
paths, every orientation of /y33, Ah,4, and show that for various orientations
of star forests, trees, and crossproduct graphs there exist irregular slabelings
analogous to the irregular labelings of their underlying graphs.
We develop the topic of irregular orientations of a graph G. An irregular
orientation of a graph G, O, is an orientation of a graph which has the error
correcting degree matrix typical of an irregular digraph. We show a class of
graphs that have irregular orientations.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signei
'ichael Jacobson
DEDICATION
We would like to dedicate the thesis to the numerous ski resorts that can
be found in Colorado including Copper Mountain and Winter Park. Having
learned to ski at Copper Mountain, the author cannot help but attribute some
of his appreciation for learning to the ski industry and to Copper Mountain in
particular. While skiing has been subsumed by snowboarding throughout most
of the country, we raise a toast to those skiing purists who manage to set the
snowboard aside a few times each year and strap on their skiboots.
ACKNOWLEDGMENT
This thesis continues the work of several notable mathematicians and in par
ticular is modeled after a former student of my advisor, Hal Hackett. His thesis
served as the foundation for at least two major pieces of this thesis. With
out his work, the current thesis would probably not have seemed feasible from
the outset. In addition, we must acknowledge the work of Z. Skupieri and a
number of other Polish mathematicians including but not limited to J. Gorska,
Z. DziechcinskaHalamoda, Z. Majcher, J. Michael. Of course, the entire topic
was modeled after work by Chartrand, Jacobson, Lesniak, Oellerman, Ruiz, and
Saba. The topic of irregularity strength for graphs is storied and we would also
be remiss if we did not mention the paper by Gargano, Kennedy and Quintas.
Closer to home there are a number of people in the department we would like
to thank. Of course, all the members of the committee helped out. Among the
graduate students, we would like to thank Arthur Busch, Angela Harris, Nathan
Kurtz, Shelley Speiss, and Craig Tennenhouse for their cameraderie. A special
thanks goes to Michael Ferrara whose meticulous criticism and support were
essential for getting the project off of the ground and keeping it in the air.
CONTENTS
Figures .................................................................. x
Tables................................................................. xiii
Chapter
1. Introduction to Graph Theory......................................... 1
1.1 Terminology.......................................................... 1
1.2 Degree sequences and Digraphs.............................. 7
1.3 Operations on Graphs................................................ 15
2. Irregular Labelings................................................. 16
2.1 History ............................................................ 16
2.2 The Motivation behind Irregular Labelings......................... 16
2.3 Lower Bounds........................................................ 20
2.4 Survey.............................................................. 21
2.5 General Results and Bounds.......................................... 23
3. Introduction to Digraph Irregularity Strength ...................... 26
3.1 Irregular Labelings and the Main Definition......................... 26
3.1.1 The parameter s................................................... 26
3.1.2 Graphs and Irregular Orientations ................................ 27
3.2 Irregular Digraphs ................................................ 27
3.2.1 The Seminal Idea for Arc Minimal Digraphs......................... 28
3.2.2 Arc Minimal Digraphs with Arc Multiplicity 2...................... 30
vii
3.2.3 Berges Theorem...................................................... 32
3.3 Relationship with Graph Irregularity Strength......................... 33
3.3.1 NearlyIrregular Graphs.............................................. 33
3.3.2 More Parameters...................................................... 34
3.3.3 Fairness and Cost.................................................... 35
4. The Parameter A.......................................................... 37
4.1 The Parameter A........................................................ 37
4.2 Minimizing and Maximizing A............................................ 38
4.3 Discussion............................................................. 39
4.4 Disparity ............................................................. 41
5. The Complete Graph and Tournaments.................................. 42
5.1 sH(Tn) : A different definition for irregularity strength of digraphs . 42
5.2 Tournament Algorithm: s(Tn)............................................ 43
5.2.1 Variations on the Algorithm.......................................... 46
5.2.2 Collections of Tournaments........................................... 49
5.2.3 Multipartite Digraphs................................................ 51
6. Small Irregularity Strength.............................................. 55
6.1 s = 2, and disp =1..................................................... 55
6.2 If n > 1, s(Knn) 2.................................................. 56
7. On Path Irregularity Strength and Disparity......................... 88
7.1 Paths, Cycles, and the Rooted Circuit Packing Lemma.................... 88
7.1.1 Unions of Directed Cycles............................................ 89
7.1.2 Unions of Directed Paths ............................................ 90
7.2 Irregular Labelings of Antipaths...................................... 94
viii
7.3 More on Disparity ................................................ 98
7.3.1 The Band: Ah x Cn................................................. 99
7.3.2 The Wheel ....................................................... 105
7.3.3 Anticycles....................................................... 107
7.3.4 Ladders.......................................................... 109
8. Forests............................................................. 115
8.1 Star Forests..................................................... 115
8.2 History of the Problem for Graphs ............................... 116
8.3 Mixed Stars...................................................... 117
8.4 Conclusions...................................................... 119
9. Irregular Orientations and Conclusions.............................. 120
APPENDIX
A. Two Proofs By Cases............................................... 123
A.l Proof by cases of 6.15: An overview.............................. 123
A.2 Cases of X2.2 has (27?)avoiding irregular 2labelings........... 124
A. 3 Cases of X'3,3 has (0, 0)avoiding (0, l)labelings.............. 133
B. A Proof of Theorem 3.3 141
References............................................................. 151
IX
FIGURES
Figure
1.1 A Maximally NearIrregular Graph has 2 vertices of the same degree. 11
2.1 There is no unique irregular labeling of P4............................ 20
3.1 The paw has an irregular orientation................................... 27
3.2 Realizing Arc Minimal Digraphs of Strength 2........................... 30
5.1 Two cases in the final step of the tournament algorithm ............... 45
6.1 A (0, 0)avoiding irregular (0, l)labeling of the Hamiltonian regu
lar orientation of gives rise to this irregular 2labeling of the same
orientation of Ad,4 pictured here on the torus.................. 60
6.2 A (0, 0)avoiding irregular (0, l)labeling of one of the regular ori
entations of AG,4 gives rise to an irregular 2labeling of the same
orientation of Ad,4 pictured here on the torus.................. 63
7.1 The closed trail in Ad and irregular labeling of C8 associated with
the deBruijnlike sequence 11312332................................ 88
7.2 A symmetric rooted circuit decomposition of K4 with r?4 = 2, n2 = 2,
n3 = 5, n4 = 7..................................................... 91
7.3 A minimal irregular labeling of A5 and the resulting minimal labeling
of Ag................................................................. 96
7.4 Pi..................................................................... 98
7.5 Case n = 4 in the construction of the antiband.................... 102
7.6 Case n = 5 of the construction of the antiband.................... 103
x
7.7 Case n = 6 of the construction of the antiband............ 103
7.8 The labelings of ascending cases of the orientation of the wheel from
Theorem 7.16 have similar vertex weights................... 106
7.9 The ascending cases of the anticycle have similar labelings. 107
7.10 Case n = 7 of the construction of the antiladder............ Ill
7.11 Case n = 8 of the construction of the antiladder............ Ill
7.12 Case n = 9 of the construction of the antiladder............ 112
9.1 A counterexample........................................... 121
A.l Theorem 6.15 Base Cases: Part 1.............................. 126
A.2 Theorem 6.15 Base Cases: Part 2.............................. 128
A.3 Theorem 6.15 Base Cases: Part 3.............................. 129
A.4 Theorem 6.15 Base Cases: Part 4.............................. 132
A.5 Theorem 6.13: Case 1 ....................................... 134
A.6 Theorem 6.13: Case 2........................................ 135
A.7 Theorem 6.13: Case 3........................................ 135
A.8 Theorem 6.13: Case 4........................................ 136
A.9 Theorem 6.13: Case 5........................................ 136
A. 10 Theorem 6.13: Case 6........................................ 137
A. 11 Theorem 6.13: Case 7........................................ 137
A. 12 Theorem 6.13: Case 8........................................ 138
A. 13 Theorem 6.13: Case 9........................................ 138
A.14 Theorem 6.13: Case 10....................................... 139
A. 15 Theorem 6.13: Case 11....................................... 139
A. 16 Theorem 6.13: Case 12....................................... 140
xi
A.17 Theorem 6.13: Case 13
140
xii
TABLES
Table
2.1 A summary of progress in the study of graph irregularity strength . 25
7.1 A table bounding the disparity of some graph classes from below and
listing exact values where possible; notice some of the values have
been proven to hold for large n only ....................................... 109
xm
1. Introduction to Graph Theory
Graph theory is the study of graphs and graph parameters. Sometimes a
thorough study of two graph parameters will lead to a better understanding
of the relationship of the two parameters or a discovery of a third important
parameter which is a function of the first two parameters.
There are various ways of recording the adjacency matrix of the graph, i.e.,
efficient ways of describing the edge set and vertex set of a graph. By defining a
digraph and the degree sequence of a digraph, the density of a graph or digraph
is given, but the degree sequence communicates great deal more information.
Because a degree sequence is not unique up to graph isomorphism, the degree
sequence of a graph does not give all the information about a graph. After
making the cursory definitions, we define the powers of a graph G.G2..... Gk
and distinguish the power operation from the crossproduct operation as well as
the lexicographic product operation.
1.1 Terminology
First define a graph and some substructures of the complete graph including
paths, trees, cycles, circuits, walks, multipartite and bipartite graphs in the
following way.
Definition 1.1 ([36]) A simple graph G is a set of two sets V and E where E
is a set of unordered pairs of elements from the vertex set. The order n(G) of a
graph is the cardinality ofV. The size of a graph, e(G), is the cardinality of E.
1
There appears to be one way of defining a graph, and this description or
definition seems to recur through the literature of graph theory, though no one
author seems to be the originator or inventor of the concept of a graph.
Theorem 1.2 ([36]) The maximum size of a simple graph where V" = n is
This theorem is easy to see because each vertex in a simple graph (graph
where no double edges appear) is n 1 where n is the order of the graph. Now,
because each edge has two endpoints, we get that the maximum number of edges
in a simple graph is ("2r1. This edge count is clear by what we call the First
Theorem of Graph Theory [10]: every simple graph has the property that the
sum of the degrees in the degree sequence of a graph is twice the number of
edges in the graph.
Definition 1.3 ([36]) A clique or complete graph Kn is a simple graph on n
vertices of maximal size.
Definition 1.4 ([36]) An isomorphism from a simple graph G to a simple
graph H is a bijection f : V(G) V(H) such that uv Â£ E(G) if and only if
f(u)f(v) Â£ E(H). We say G is isomorphic to H if there exists such a function
/
The concept of a subgraph can be used to understand the whole of graph
theory as the study of subgraphs of the complete graph.
Definition 1.5 ([36]) A simple graph H is a subgraph of G when there exists
a subset ofV(G) and a subset of E(G) that when taken together as a graph G'.
2
gives G' isomorphic to H. We write H C G if H is a subgraph of G.
Definition 1.6 ([36]) The neighborhood of a vertex v, N(v) {U : u E
U if uv E E(G)}. The closed neighborhood of v, denoted jV[t'], = N(v) U {v}.
Definition 1.7 ([36]) The neighborhood of a subset of vertices U of V(G) is
the union of the neighborhoods of the vertices of U.
The degree of a vertex is the fundamental idea we will be discussing. The
degree sequence of a digraph or graph appears to be the next step along the sets
of information from the density of a graph or digraph that create an ascending
tower of information, and which terminate with the full incidence or adjacency
matrix of the desired graph or digraph.
Definition 1.8 ([36]) The degree of a vertex v written deg(v) is = \U : u E
U if uv E E(G)\. We call N(v) the neighborhood of v and define it to be the set
of vertices adjacent with v. Notice Ar(u) = deg{v).
Definition 1.9 ([36]) The minimum degree of G written 6(G) is the
min{deg(v) : v E V'(G0}.
The maximum degree of G written A(G) is max{deg(v) : v G V(G)}.
Definition 1.10 ([36]) Given a graph G of order n, an nterm list of the de
grees of G is the degree sequence of G. We denote the degree sequence of G by
7r(G). Given a sequence S of n integers, we say that the sequence S is graphic
if there exists a graph G of order n such that n(G) = S.
3
To shorten notation, if the degree i has multiplicity k in a degree sequence,
we sometimes write ik to record those terms of degree i in the degree sequence.
The ErdosGallai theorem, presented as a basic theorem in most courses, re
lies on very fundamental, though quite difficult proof techniques and establishes
a very deep, though not quite intuitive idea.
Theorem 1.11 (ErdosGallai) A sequence ir: dp < dp_x < < di of non
negative integers whose sum (say s) is even is graphic if and only if
i di < k(k 1) + min{dj, k} for every k such that 1 < k < p.
Theorem 1.12 (HavelHakimi) For n > 1 a nonincreasing integer list it =
di, d)...., dp withp terms is graphic if and only ifn' is graphic where it' is obtained
from it by deleting its largest element dx a,nd subtracting 1 from its dx next largest
terms. The only 1term graphic sequence is d,\ = 0.
As a first step toward understanding the basic structural aspects of a graph,
consider the following concept of a walk.
Definition 1.13 ([10]) A walk is a list V\, ey, V2,.... e^, Vk of vertices and edges
such that for all 1 < i < k, the edge el is the unordered pair The length
of a walk is the number of edges in the walk. Walks are often abbreviated by just
listing the order of vertices.
Definition 1.14 ([10]) A trail is a walk with no repeated edge.
Definition 1.15 ([10]) A circuit is a closed trail; that is, a circuit is a trail
whose initial and terminal vertices are identical.
4
Definition 1.16 ([10]) The adjacency matrix of G. A(G) is an n by n square
m,atrix which has an entry at the uv and vu coordinate if and only if u ~ v in
G; that is, if uv G E(G). The powers of A(G) : A(G), A2(G), A3(G)..... are just
the powers of A(G) under standard matrix multiplication.
Theorem 1.17 ([10]) The number of uvwalks of length j in G is given by the
uvcoordinate of A^(G).
Definition 1.18 ([10]) A uvpath is a walk from u to v which is a subgraph
of G such that no vertex or subsequence of two vertices repeats.
Definition 1.19 ([10]) A path of order n, Pn. is a tree with degree sequence
(l)2,{2)n~2.
Definition 1.20 ([10]) A graph G is connected if there is a uvpath in G for
every pair of vertices u. v G V(G).
Definition 1.21 ([10]) A component of a graph G is a connected subgraph H
of G such that for no v G V(H), u G V(G H), does G contain a uvpath.
Definition 1.22 ([10]) A cycle of order n, Cn, is the unique connected simple
graph with degree sequence (2)n.
Definition 1.23 ([10]) A tree Tn is a simple graph which has no cycles as
subgraphs, but which has n(G) 1 = e(G).
A tree is an example of a bipartite graph.
Definition 1.24 ([36]) A bipartite graph has a bipartition of its vertex set such
that no edge has both endpoints in the same partite set of the bipartition.
5
Theorem 1.25 ([36]) Bipartite graphs have no odd cycles.
Definition 1.26 ([36]) A biclique Km
tices in one partite set, n vertices in the other partite set and maximum density.
Now we develop the idea of circuits.
Definition 1.27 ([10]) An Eulerian circuit C is a circuit in G such that
E(G) C E{C).
Theorem 1.28 ([10]) A connected graph G is Eulerian if and only if the degree
of every vertex in G is even.
Definition 1.29 ([10]) A cycle in G is a closed uvwalk in G such that no
vertex repeats.
Eulerian graphs and multigraphs will be especially important in our study of
irregular labelings of digraphs. Specifically, we will use rooted circuits which we
pack in a special directed multigraph called a complete symmetric digraph with
loops. The complete symmetric digraph with loops has applications in Chapter
7, but notice here that a closed circuit is Eulerian and that any connected graph
that decomposes into Eulerian circuits is necessarily itself Eulerian.
Definition 1.30 ([10]) We say a subgraph H of G spans G ifV{G) C V(H).
Again, subgraph containment is vital to one of the techniques we will apply
to the study of digraph irregularity strength. First, notice any simple graph is a
subgraph of Kn and similarly that any simple digraph with loops is a subdigraph
of the complete symmetric digraph with loops. Meanwhile, every oriented graph
6
can be taken as a subdigraph of some tournament even though this is not the
case for simple digraphs. This is because simple digraphs are a superset of
oriented simple graphs; simple digraphs can have two arcs between a pair of
vertices which are not identical, 2 copies of the same edge directed in opposite
directions.
Definition 1.31 ([10]) A Hamiltonian cycle is a spanning cycle of G.
Definition 1.32 ([10]) A spanning tree is a simple spanning subgraph H of G
which is a tree.
Theorem 1.33 ([10]) All connected graphs have a spanning tree.
Definition 1.34 ([10]) A factor is a spanning subgraph of G which, is regular.
Definition 1.35 ([10]) The complement of a graph G is the ordered pair
where H is the complete graph on the vertex set, of G.
Digraphs come in many types. There are simple oriented graphs, oriented
graphs with loops, and looped and loopless directed multigraphs. The funda
mental theorem of digraph theory is that the sum of outdegrees are equal to
the sum of indegrees in any digraph.
1.2 Degree sequences and Digraphs
We begin by defining an oriented graph.
Definition 1.36 ([5]) An orientation G of the graph G is an ordered pair of
sets V(G),A(G) where we have V(G) = V(G) and the arc set of G is just a
7
set formed from the edge set of G by adding some direction to each, edge, that is
we replace each unordered pair with exactly one ordered pair of vertices. If the
ordered pair (u, v) G A(G) then we say that uv is directed from u to v and that
u beats v. We often abuse notation by saying ub G A{G).
Definition 1.37 ([5]) The degree of a vertex in an oriented graph G is an
ordered pair deg(v) (a, b) such that the cardinality of the set of arcs ini G
A(G) is a, and the cardinality of the set of arcs uv G A(G) is b. We also say
deg+(v) = a, deg~(v) = b and degtot(v) = a + b. The term
5(G) = min{x : x = min{d,eg+{v),deg~{v)} where v G Vr(G)}.
Similarly,
<5+((?) = min{deg+(v) : v G V(G)},
S~(G) = min{
and
5tot(G) = min{de(/+('t;) + deg~(v) : v G V(G)}.
Terms A0, A+, A", Atot are defined analogously.
Definition 1.38 ([5]) A source is a vertex with deg 0. A sink is a vertex
with deg+ = 0. An outdirected orientation of a graph is an orientation of
a graph with one source w and deg~(v) > 1 for all v w. An indirected
orientation of a graph is an orientation of a graph with one sink w and deg+{v) >
1 for all v w. An antigraph is an orientation of a graph where every vertex
is a source or a sink.
8
Tournaments have many special properties: among them we find that every
tournament has at least one king, [10], and every tournament is traceable [9].
Only two complete graphs can be oriented so that the}7 are antigraphs: Rf and
k2.
Definition 1.39 ([5]) A tournament is an orientation of Kn.
We go over the structures which are analogous to the basic structures of
path and cycle in a graph.
Definition 1.40 ([5]) A directed path is an orientation of a path such that only
the terminal and initial vertices do not have degree (1,1).
Definition 1.41 ([5]) A directed cycle is an orientation of a cycle such that
all the vertices have degr'ee (1,1).
Definition 1.42 ([5]) We say an orientation of a graph is traceable if there is
a directed Hamiltonian path contained as a subdigraph.
Theorem 1.43 ([5]) Every tournament is traceable.
Definition 1.44 ([5]) A transitive tournament is a tournament with the prop
erty that ifwv. vw Â£ A(Tn) then ivw Â£ A(Tn).
Theorem 1.45 ([5]) A transitive tournament is acyclic.
A valuable way of viewing a tournament is in terms of its vertex degrees.
Definition 1.46 Let N0 be the set of nonnegative integers, p Â£ N0 and let
Bp = {(a,b) : a + b = p, a,b Â£ Ar0}
9
Definition 1.47 A block is a set of entries from Bp. A complete block is Bp for
some value p.
Notice that if we have a complete block then this block can be realized by a
digraph: a transitive tournament of order p realizes the block Bp_\ as a digraph.
Theorem 1.48 The transitive tournament Tn is an irregular oriented graph and
its sets of degree pairs has deg (V(Tn)) = Bn\.
Furthermore, we can describe a subblock of a block Bp as a subset of the
elements of the block Bp. Of special interest is the set of balanced subblocks of a
block Bp, that is, the subblocks whose set of inarguments sum to the same value
as its set of outarguments. More precisely, a balanced subblock, [12], Bp[mn\ is
a subblock of Bp with rnn < p elements {(ai, 6i), (a2, 62), t>mn)} where
we have
i=mn inin
bi
i1 i=l
We denote the transitive tournament of order n by Tn; there should be no
confusion with a tree of order n. We sometimes abuse notation by using Tn
to denote an arbitrary tournament of order n (see Chapter 5). An important
generalization of a tournament is called a team tournament.
Definition 1.49 ([5]) A kteam tournament is an orientation of a complete
kpartite graph.
Notice that by the pigeonhole principle every graph has two vertices of the
same degree. This is not true of digraphs, with an obvious counterexample being
the transitive tournaments.
10
3  "
3 ' , ''
2
1
Figure 1.1: A Maximally NearIrregular Graph has 2 vertices of the same
degree.
Theorem 1.50 (Landau) A nonincreasing sequence is a score se
quence of an nvertex tournament if and only if (*) < \i\=k N
A fact we wall use later is that if two vertices have the same degree in a
tournament, then those two vertices he on a directed triangle.
Definition 1.51 A multigraph M is an ordered triple
< V(M), E(M), f >
where f is a map from, the elements of E(M) into the positive integers. We
interpret the image of an edge e under f, /(e) to be the edge multiplicity of an
edge. A multidigraph is an ordered triple < V(M), A(M), / > where we allow
both uv and mi Â£ A(M). A simple digraph is a multidigraph where f(a) = 1
for all a 6 A{M). We say a graph G underlies a digraph D if V{D) = V(G)
and for all uv Â£ E(G), uv or vu Â£ A(D).
Definition 1.52 ([5]) A semicomplete digraph D is a simple digraph such that
Kn underlies D.
11
Definition 1.53 ([3]) If a graph has at most k vertices of the same degree then
we say it is kirregular.
Chapter 9 concerns itself with irregular orientations of /.'irregular graphs.
To explain what this means we will need some definitions.
Definition 1.54 ([5]) An orientation of a multigraph is a 11 onto function
from the edge set of a multigraph to the arc set of a digraph with the same vertex
set. We simply put a direction on each edge.
Definition 1.55 ([20]) A digraph D such that every vertex has distinct, degree
is called an irregular digraph.
Interest in irregular digraphs is at least two years old and we can trace
the origins of this interest back to at least two distinct sources [20], [12]. In
[20], the idea of embedding irregular digraphs in regular digraphs is developed
as are constructions wherein regular digraphs are built from blocks of irregular
digraphs that can be recovered by taking sets of vertices and looking at the
induced digraphs on those sets of vertices.
Definition 1.56 ([20]) If a graph has an orientation which corresponds to an
irregular digraph then we say it has an irregular orientation.
The problem of finding an irregular orientation of a graph seems to be a
completely new problem. A graph, with its degree set partitioned into classes
by degree, can be oriented in a specific way to partition those degree sets even
further. Notice that irregular orientations have obvious necessary conditions
12
on which they depend in order to exist. There do not appear to be any ob
vious sufficient conditions, though we will certainly explore this problem later
(Chapter 9). The idea of labeling a digraph by its degree set is a powerful one
because it guarantees that the resultant digraph has automorphism group of
order 1. Given a graph there may be more than one irregular orientation, or
all irregular orientations may be isomorphic up to digraph isomorphism. This
latter situation would mean than the original graph would have a relatively large
automorphism group compared to that of the irregularly oriented graph which
has automorphism group of order 1. Notice that if we give a graph an irregular
orientation the result is an irregular digraph or rather a digraph of irregularity
strength 1 (see Chapter 3).
Theorem 1.57 Every complete graph has a unique irregular orientation up to
digraph isomorphism.
Theorem 1.58 Every has a unique irregular orientation up to digraph
isomorphism.
Definition 1.59 We say a graphic sequence n is uniquely realizable as a simple
graph, multigraph, oriented graph, digraph, or rnultidigraph respectively if there
is exactly one simple graph, multigraph, oriented graph, digraph, or rnultidigraph
that realizes that sequence.
Next consider the theorems which concern themselves with realizations of
disequences. There are many ways of building up this foundation; we do so
here with little proof included, in the fashion followed by many of the texts that
cover the same material.
13
The following theorem by Beige tells us which sequences are digraphic.
Theorem 1.60 (Berge [6]) Let{r\,s i), (r2, ,s2),(rn, sn) be pairs of integers
with
Sn S: 1 ' ^ ^T
The pairs {(?>. }= constitute the degree pairs of a digraph with maximum
arc multiplicity rn if and only if
j=h i=n
S3  min {rt, mk } k Â£ [n] (1.1)
j=i i=i
jn i=n
= (L2)
j=i t=l
The following definitions are useful when we study realizations of degree
sequences for digraphs.
Definition 1.61 When we replace an arc wv with the pair of arcs, ux2 and xfv
we refer to this construction as an arcswap.
Notice this definition is not necessarily standard in the literature [17].
Definition 1.62 When we replace two arcs uv, x{x2 with the pair of arcs ux2
and xfv we refer to this construction as a double arcswap.
Definition 1.63 A null vertex is a vertex of degree zero. It is also called an
isolated vertex.
Definition 1.64 Selecting a hamiltonian path from a tournament is called trac
ing a tournament.
14
Definition 1.65 One sequence is majorized by another if the first sequence can
be put in a onetoone correspondence with the second such that each term of
the first sequence is less than or equal to its image in the second sequence. In
particular {(i,^)}l= majorized by if at < at and bi < b\ for all
1 < i < n.
1.3 Operations on Graphs
Next we cover the basic operations on graphs.
Definition 1.66 ([36]) The union of two graphs G and H has
GUH= < V{G)UV(H),E(G) U E(H) > .
Definition 1.67 ([36]) The join of two graphs
G A H = < V(G) U V(H),E(G) U E{H) U E([V(H), V{G)}) > .
Definition 1.68 ([36]) The direct product of two graphs
Gx H= < Kj : Vi e V(H) A Vj G V{G)},
{vijVh'k : ViVh E E(H) V VjVk G E(G)} > .
Definition 1.69 ([36]) The lexicographic product
G xlex H = < {nj : Vi G V(H) A Vj G V{G)}.
{vi,jVh,k : VjVk G E(G) V (ViVh G E(H) A j = k)} > .
Definition 1.70 The direct product of two digraphs
Gx H = < {ViJ : Vi G V{H) A Vj G V(G)},
{vijVh.k ViVh G A(H) V vfbk G A(G)} > .
15
2. Irregular Labelings
Giving a brief overview of the history involved will motivate the subject mat
ter of graph irregularity strength. We also introduce a core definition, s(G), the
irregularity strength of a graph G. Some upper bounds and existence theorems
for the parameter s(G) are given in section 2.5.
2.1 History
While graph theory seems to have originated in several different geographic
areas at varying timeperiods both because of and apart from earlier develop
ments, the study of irregular graphs and digraphs can be traced directly to a
seminal paper in the 1980s by Chartrand, Jacobson, Lehel, Oellerman, Ruiz,
and Saba paper [9], Notice that the first paper published on the subject matter,
authored by Gyarfas, [27], was actually the second submitted paper on the topic
of irregularity strength of graphs. While many authors had been aware of the
fact that every simple graph has two vertices of the same degree, it was not
until this time period that the concept of edge labels were used to distinguish
the weighted degrees of a graph.
We proceed to define some terms such as an irregular labeling and the irreg
ularity strength of a graph. The terms are analogous to the topics of an irregular
labeling of a digraph and the irregularity strength of a digraph.
2.2 The Motivation behind Irregular Labelings
Notice that the degree sequence of a graph does not always give all the
information possible about a graph. While some parameters of a graph are
16
always given by the degree sequence (such as A and 5). these parameters are
not sufficient to characterize the graph. Notice also that if S is the set of
positive integer degrees which are elements of the degree sequence, there is only
one example where the cardinality of S = V(G); the only such example is the
isolated vertex K\. This graph has the degree sequence 0 and the degree set {0}.
We have in this case that ,SV; = \ V(G) \ = 1. Except for this case there does not
exist an injection from the vertex set of a simple graph into the integers. This
follows from the following argument:
Given a simple graph G of order n > 2, there are n possible degrees for the
vertices of the graph G. namely 0.1. 2,..., n 1. However, if the degree function
is an injection of the vertex set of G. which has cardinality n, it must also be
a surjection. (It is easy to show that any injection from a finite set to a finite
set of equal size is also a surjection). Thus, we get a contradiction because if a
graph has order n and a degree of order n 1, that graph cannot also have a
vertex of degree 0.
Theorem 2.1 ([10]) No nontrivial simple graph has all vertices of distinct
degree.
It is clear by example that the previous theorem does not hold for multi
graphs whether or not we allow loops. We will show that for all simple graphs
with the exception of simple graphs containing 2 Ad or K2 as components, there
exists a map from the edge set to an multiedge set < E(G),f(e) >. where
/ : E(G) * Z+ such that the multigraph which is the image of our graph
under / has all vertices of distinct multidegree. By an irregular graph we mean
either Ad, or multigraph whose vertices all have distinct degrees. Irregular
17
labelings help demonstrate what an irregular multigraph is with examples from
graph theory.
Consider an edge labeling of a graph G f : E(G) > Z+. We define a vertex
weighting induced by our edge labeling to be
g :V{G)^ Z+
where
9(v) =
vxE(G)
Definition 2.2 ([9]) If our vertex weighting is such that each vertex has a dis
tinct weight we say our edge, labeling is irregular.
Irregular labelings are a wellresearched topic. Changing the context slightly
expands the topic in a new way which enhances the preexisting research.
Now to show our previous claim, suppose that G has no trivial components
of the form 2Aj or Ah. Then it is clear that any map / which is injective into the
subset of Z+ which contains only powers of 2 is an irregular labeling of G. The
vertex sums are sums of binary powers and are all distinct unless two vertices
are incident with all the same edges or two vertices are incident with no edges.
Notice the map / can be any injection from E(G) into {x : x = 2k, k G Z+j.
With this existence theorem clear we move on to consider irregular labelings
of simple graphs G such that the largest value k G f(E(G)) is relatively small
compared to 2^^ where / is an irregular edge labeling.
Theorem 2.3 ([9]) The irregularity strength of all connected graphs of order
greater than or equal to 3 is defined.
18
Proof: Let G be a connected graph of order > 3. Let E(G) 
{ei, e2,e9}. Assign the weight 2l_l to the edge e, for 1 < i < q. Each vertex
then is assigned a weight equal to the sum of distinct binary powers. Thus the
weights are distinct because no two vertices are incident the same edges.
To see that the answer is not always of the correct order of magnitude,
consider a class as broad as the connected graphs other than K3. In these cases,
one upper bound on s(G) is but there is a second upper bound which
bounds the irregularity strength of this class of graphs above by < n 1, where
n is the order of our connected graph.
Definition 2.4 ([9]) The set of irregular labelings of G is denoted 1(G).
We will in fact determine in some cases the smallest value of k Â£ f(E(G))
where / is an irregular labeling on the edge set of G across all / Â£ 1(G). We
can now define the irregularity strength of a graph G.
Definition 2.5 ([9]) The irregularity strength of G, denoted s(G), is defined by
s(G) = min max /(e).
fl(G)eeE(G)
The irregularity strength of a graph G gives the smallest arc multiplicity of
an irregular multigraph M such that G underlies M. Now that we have shown
that the irregularity strength of G is defined in a variety of examples, we can
turn to the problem of determining the irregularity strength of a graph G. The
determination of the irregularity strength of a graph G generally has two parts:
first, an irregular labeling of the graph is exhibited, and second, we demonstrate
19
(1) (4) (5) (2)

1 3 2
(1) (3) (4) (2)

1 2 2
Figure 2.1: There is no unique irregular labeling of P4.
that the largest label used in the given irregular labeling is in fact the minimum
maximum labeling across all irregular labelings of G.
2.3 Lower Bounds
It is not clear in general how to determine s(G). In many cases the following
parameter A(G) is within an additive constant of s(G') and in fact, in many of
the cases, this constant = 0. One of the nice features of this lower bound, which
is completely determined up to the degree sequence, is that proving s(G) = A(G')
amounts to constructing an irregular labeling that achieves the lower bound.
Theorem 2.6 ([9]) If G is connected with the order of G > 2 then let Pi rep
resent the number of vertices of degree 1 in G. Then s(G) > Pi+l~l .
Proof: Let I be the number of labels required to label G. Then pt. the
number of vertices of degree i has pt < iÂ£ i + 1. So then Â£ > + 1. Thus
s(G) > Enii + 1 = aipl .
The preceding theorem motivates the next theorem; we include both the
orems to motivate a general lower bound in the study of graph irregularity
strength.
20
Theorem 2.7 ([9]) If G is of order > 3 and Pi and pj represent the vertices
having degree i and j respectively i < j in G, then
s(G)>
(EUiPk) + ?: 1
Proof: Let I be the number of labels required to label G. Then Y^kiPk,
the number of vertices of degrees between i and j has Ylk^iPk E jl i + 1.
Thus s(G) >
(E {=iPk)+il
j
Definition 2.8 For a graph G with pt vertices of degree i, let
A(G) = maxo
Notice that A(G) is a lower bound for s(G).
These results form what was at one time a rough bound which later evolved
into a function with a name and finally the standard lower bound. The thrust of
the subject is just beginning to turn towards estimations of upper bounds and
away from exploring the problems with the A(G) function.
2.4 Survey
There has been a great deal of collaboration in the subject of irregularity
strength and it is rare that authors tackle the problem on their own. Unless
there is a complete characterization of the values of s(G) for all simple graphs
G there will be a wealth of families of graphs whose irregularity strength can
be partially or completely determined in the future. Because in many cases the
irregular labelings of a graph are not unique, especially when the labeling allows
21
labels greater than s(G), finding an irregular labeling can be done in a relatively
short amount of time.
The irregularity strength of some classes of graphs are known.
s(Kn) = 3 n > 3.
s(Cn) =
n 2 for n = 0 mod 4,
n+1 2 for n = 1,3 mod 4,
n+2 2 for n = 2 mod 4;
m for r? = 1 mod
m +1 otherwise.
There are a number of published papers on the topic of irregularity strength
of graphs. The general strategy in the study of irregularity strength has been to
pick a class of graphs, calculate A and then produce a construction that achieves
A. There has been a movement toward calculating general bounds or finding
a property which completely determines irregularity strength for a family of
graphs. A table of results, Table 2.1, follows.
Most of these results are difficult to obtain. The constructions which show
s(G) = A(G) are involved. But notice that one of the published results [32]
22
(on tP$) demonstrate that the lower bound of A(G) cannot be achieved using
counting arguments that depend on the structure of the family of graphs being
considered.
2.5 General Results and Bounds
Finding a general upper bound for the strength of all graphs G is difficult
and depends in part on using spanning trees and the congruence method. No
tice there is a simple example to which the general upper bound of n 1 for
connected graphs of order n does not apply. This example (A^) is unique and
the irregularity strength achieves a value of n = 3.
Theorem 2.9 (Nierhoff [35], Aigner and Triesch [1]) If the irregularity
strength of a connected graph G is defined it obeys s{G) < n 1 unless G = K:i.
Most of the upper bounds which have been determined for special classes of
graphs are based on the minimum and maximum degree. The proofs rely on two
techniques, either using the congruence method to find special spanning graphs
and then determine a labeling of this spanning graph explicitly or through the
use of the probabilistic method [19],
Theorem 2.10 (Frieze, Gould, Karonski, Pfender, [19]) Let G be a graph
with no isolated vertices or edges
If A < [(n/ln n)1/4J, then s(G) < 7n( + ^),
If [(n/ln n)1/4J < A < [n1/>2J, then s(G) < 60n/8,
If A > _7?T2J + 1, and 6 > [6 In n], then s(G) < 336(ln n)n/S.
23
The following result is simpler to state and completes a program for bound
ing more sharply all graphs given A and S.
Theorem 2.11 (FGKP [19]) Let G be a graph with no isolated vertices or
edges. If n is sufficiently large, then s(G) < 1 4n/<51/2.
Finally, we state a result of Ebert, Henuneter, Lazebnik and Woldar [14].
As the number of available labels increases, the number of irregular labelings
increases slower than a polynomial in the number of available labels. The poly
nomial has a leading exponent that is fixed two less than the cardinality of the
edge set. The theorem is more formally stated in Theorem 2.13.
Definition 2.12 Let irr(G, Â£) be the number of irregular labelings of a graph
when Â£ labels are available.
Theorem 2.13 (Ebert, Hemmeter, Lazebnik, and Woldar [14]) Irr(G.X)
C7 + CiC91 = 0(Qq~2) as Â£ > oc where q = \E(G)\.
24
Authors Graph Strength Year
Chartrand, Jacobson, Lehel, Oellerman, Ruiz, Saba [9] An 3 1986
Gyarfas and CJLORS [27],[9] ^m,m 3 m even 4 m odd 1988
Faudree, Jacobson Lehel and Slielp [16] A rn(fc) rn / 2 3 1989
Faudree, Jacobson Kindi and Lehel [15] tKp p = 4 p > 5 r^i r^i 1991
Gyarfas [30] Kn mK2 2 or 3 2 only if n = 4m or 4m+l, 4m1 1989
Ebert, Hemmeter Lazebnik and Woldar [14] A2 x Pn fA(G') + 1] n=l mod 6 [A(G)1 otherwise 1990
Ebert, Hemmeter Lazebnik and Woldar [14] Wheel n= 4 or 5 n > 6 [A(G) + 1] TA(G)1 1990
Ebert. Hemmeter Lazebnik and Woldar [14] Qk TA(G)1 1990
Togni [34] Cm X Cn \{rnn + 3)/4] 1997
Amar, Togni [2] Tree with no vertices degree 2 number of pendant vertices 1998
Table 2.1: A summary of progress in the study of graph irregularity strength
25
3. Introduction to Digraph Irregularity Strength
In [30], Hackett extends the notion of irregularity strength to digraphs.
We accomplish this extension in a different fashion, but some results overlap.
Meanwhile in [12] a specific type of irregular digraphs is characterized. These
irregular digraphs have irregularity strength 1 according to our definitions.
3.1 Irregular Labelings and the Main Definition
Consider an arc weighting of a digraph D f : A(D) > Z+. Define a vertex
labeling induced by our arc weighting to be
g:V(D)^(Z+U{0})x(Z+U{0}).
where
gw = ( f(xv))
vxeA(D) xv^A(D)
If the arc labeling is such that every vertex label is distinct, then the labeling
is said to be irregular [18]. Let 1(D) denote the set of irregular labelings of a
digraph D [18].
3.1.1 The parameter s
We will define s(D), the irregularity strength of D in an analagous manner
to that of graph irregularity strength and refer to an irregular labeling of D
with s arc labels available as an irregular slabeling. Furthermore, we may use
the term irregular sweighting of the digraph referring to the weighted vertex
degree pairs if the context is perfectly clear and we want to emphasize some
point about the vertex weights.
26
Figure 3.1: The paw has an irregular orientation.
Definition 3.1 ([18]) The irregularity strength of a digraph D is defined as
s(D)
min max fie).
ftr(D) eeA(D)
Unlike graphs, there are digraphs D with s{D) = 1, such as the transitive
tournaments, a directed TV and the orientation of the paw pictured in Figure
3.1.
3.1.2 Graphs and Irregular Orientations
Notice that not every orientation of the paw is irregular. This is the case
with many graphs. As we shall see here when we discuss the property of being
an irregular digraph, there exist graphs having some, but not all orientations
irregular.
3.2 Irregular Digraphs
In [12], DziechcinskaHalamoda, Majcher, Michael and Skupien determine
all the irregular digraphs on n vertices which have the minimum number of arcs
possible. While there is no program for determining all the digraphs which are
irregular given a specific order of the digraph in [12], there are a number of
valuable ideas for transforming an irregular digraph with the minimum number
of arcs to an irregular digraph with a greater number of arcs using arc swaps
and arc additions. In particular, we explore the idea of cataloguing digraphs of
a given irregularity strength in Section 3.2.3 with reference to Berge:s Theorem.
3.2.1 The Seminal Idea for Arc Minimal Digraphs
Definition 3.2 For a positive integer n, the nonnegative integers rn and mn
are defined such that T\ = 0 and mi = 1 and
n 1 + 2 + ... + Tn + mn, 1 < m,n < Tn + 1
and so
mn = n Tn{rn + 1).
The digraphs D, which are irregular and have minimum arc sum can be
characterized in terms of their degree sequence.
For a given positive integer n, denote by nm the class of all sets 7r of ordered
pairs of nonnegative integers such that the following three conditions hold: (1)
7r is an nelement set; (2) the sum of the terms of 77 is (0,0); (3) the absolute
values of the arguments of the terms of 7r have the minimum sum among all 7i
satisving (1) and (2).
By Bs[k], where 0 < k < s + 1, we denote a kelement subset of the set Bs.
Theorem 3.3 Let n be a positive integer and let rn and mn be given as above.
For n > 2, 7T 7rm if and only if ir has one of the following four forms:
28
i. 7r = {(0,0)} is the only member of 7rm for n=l, tt171 = {Bo},
ii. 7r = U[lo 1 Bi U BTn [mn],where the set BTji [m.n\ is balanced and mn is even
or rn is even,
iii. 7r = Bi {(aP)} U BTri[rnn + 1], where (a,(3) E BTn_i, the set
+ 1] U {a. /}} is balanced and both numbers r and mn are odd,
iv. 7T = [XZq1 Bi U BTji [mn ~ 1] U {(a,/?)} where (a,p) E BTn+1, the set
Â£?TrJm 1] U {(a, d)} is balanced and both numbers rn and mn are odd.
Theorem 3.4 Let n be a positive integer such that rn and mn are both odd.
Then a set n described in case (in) of the previous theorem exists for any pair
(a. b) E BTn_ i if mn < rn, otherwise mn = rn and then tt exists for a = b =
\{rn 1) only. Moreover, a set tt described in case (iv) exists for any (a,b) E
BTn+1 if mn 1. otherwise tt exists for a = b = (rn + 1) only.
Theorem 3.5 The minimum size of a digraph D of order n with s(D) = 1 is
equal to en where
rn(n (rn + l)(rn + 2)) + 1 if rn and mn are odd,
2en <
Tn{n i(T + l)(r + 2)) otherwise.
The proof of Theorem 3.5 relies on the proof of Theorem 3.3. In [12], the
authors give a construction and sketch the proof of Theorem 3.3. Some of the
details are left to the reader. We have included a proof of Theorem 3.3 in
Appendix B.
29
Figure 3.2: Realizing Arc Minimal Digraphs of Strength 2
3.2.2 Arc Minimal Digraphs with Arc Multiplicity 2
We use the same notation from Section 3.2.1. For this section, we use the
notation D2 to describe the digraph whose adjacency matrix = 2M if M is the
adjacency matrix of D; this is not to be confused with the square of a digraph,
despite the identical notation. Furthermore, if there is a double arc VjVj write it
as 2viyj.
Example 1 We notice that the arc minimal digraphs with degree sequences of
the form Bp = {(a, b) : a + b = p, a,b G A0} can always be realized in the
following way:
If p = 2k is even, then we can realize the sequence Bp as T2 x K2.
We can see this is arc minimal in the following way. Each vertex has at least
one odd element, in its degree pair since the two elements sum to an odd total.
So there is at least one arc of multiplicity 1 incident each node in the realization.
The fewest number of nodes thus occurs if every other arc has multiplicity 2.
This is exactly the case above. Notice that there exists a. realization of a di
graphic sequence with t odd outterms with just t arcs labeled with a 1. If a pair
of vertices both have two arcs labeled 1 incident from each of them respectively,
the intersection of their 1labeled outneighbors has cardinality either 0,1, or 2.
In the case that the cardinality is 2, replace vx\, vx2, ux\, ux2 with a double
30
arc from v to x\ and a double arc from u to x2. Similarly, given cardinality 1,
we can replace raj, vx2, ux\, ux3 with a double arc from v to xy. an arc from
u to Xo, and an arc from u to x3. If every pair of vertices that are incident to
an arc labeled 1 have disjoint outneighborhoods, then there are exactly t arcs
that are 1labeled and t odd outdegrees.
If p is odd, the following digraph realizes Bp. Let V(D) = {nl7 ...v2k+i}
where here 2k + 1 = p. Then let
A{D) = {2ViVj : 1 < i< j < k; j 7^ i + 1}
U {ujUj+i : 1 < i < k 1}
U {2 v^j :k + l
U {2v2k+iVi : 2 < i < k 1}
U {2ViVi+k : 1 < i < k}
U {V2k+\VuV2k+lVk}.
It is clear there is no realization of Bp with fewer arcs in this case. There
are exactly ^ arcs labeled 1.
If Bp[mn\ has mn nonzero, we cannot find a general construction for the
case when mn 7^ 0.
We have just determined the minimal number of arcs in digraphs of strength
2 for cases when the number of vertices in the digraph has the form (^) and
constructed realizations of one instance of such digraphs in the case when p is
odd and p is even. In the case where p is odd the minimum number of arcs is
^ + 2^1 + 2. In the case where p is even the minimum number of arcs is f + 2
31
It does not appear that we will be able to find a (dosed form (with proof) for
the number of arcs in the arc minimal underlying digraph of an irregular super
digraph of order n. if we allow arc multiplicity m in the irregular superdigraph.
3.2.3 Berges Theorem
Here we restate Berges Theorem.
Theorem 1.60 Let (/i, Si), (7*2, S2),,, (r, sn) be pairs of integers with
Sn &n 1 '*1
The pairs {(r^,s*;)}Â£:: constitute the degree pairs of a digraph with maximum,
arc multiplicity m if and only if
j=k i=n rj < min{Si, mk} j=1 i=l (3.1)
i=n i=n xi = ri i=1 z=l (3.2)
Now consider all irregular sequences of vertex degree pairs of a given or
der and then use Berges theorem to test and construct the graphic sequences.
Once a single realization has been constructed we use capacitated arcswaps
to characterize the ,sirregular digraphs fully. Despite the exhaustive nature of
the program, note that if there exists a realization of an irregular sequence of
degree pairs, there is an exact count on the number of irregular multidigraphs
which realize a given irregular disequence. There is thus an upper bound on
the number of simple digraphs which realize an irregular disequence.
Theorem 3.6 Given a realization of an irregular disequence the number of
realizations of that disequence (with multiple arcs and loops allowed) is given
32
by
\A{D)\'.
n r'
Proof: This equality is proved by induction on the number of vertices and
arcs. Clearly vertexaddition of v leaves the product fixed. Now add an arc a
incident the new vertex v. By induction the number of arclabeled realizations
is d.! because we can leave the new arc fixed or swap the endpoint of a not
incident with v with the corresponding endpoint of any of the (T 1) arcs in
a double arc swap for each of the (A 1)! realizations. But then to reduce
to the number of realizations up to arcisomorphism divide by the order of the
subgroup of the arc permutation group that fixes the number of arcs in each
inneighborhood and outneighborhood.
3.3 Relationship with Graph Irregularity Strength
3.3.1 NearlyIrregular Graphs
Definition 3.7 The maxim,ally nearirregular graph of order n is the graph with
degree sequence 1, 2, 3,..., ((n l)/2)2, (n + l)/2,.... (n 1) when n is odd and
1, 2, 3...., (n/2)2, ((n + 2)/2),..., (n 1) when n is even.
Theorem 3.8 The graph irregularity strength of the maximally nearirregular
graph of order n is 2 for all 3 < n.
Proof: Suppose we have the maximally nearirregular graph G on n ver
tices. Then every vertex except 2 have different degrees. So the irregularity
strength of G is greater than 1. But we can easily label the edges of G with
two labels so that the corresponding multigraph N has a nonrepeating degree
sequence. In the case that n is even, label G with 2s and the change edge labels
33
on the edge upy+i from 2 to 1 where i > (n/2) + 1 and i is even. In the case
that n is odd label the edges wit h 1 and then change the edges ViVi+1 from 1 to
2 where and i > \n/2j + 1 and i is even.
Example 3.9 For all such maximally nearirregular graphs, rank the vertices
by degree, arbitrarily choosing which of the two vertices of the same degree comes
first in the ranking. Then direct all arcs from the higher ranked vertex to the
lower ranked vertex. We get an irregular orientation for the maximally near
irregular graph of each order in this way.
Theorem 3.10 Graph strength of underlying graph is always greater than or
equal to digraph irregularity strength.
Example 3.11 Consider the Hackett graph Kn rnK2 where rn = sjri with no
irregular orientation. Because the strength of the underlying graph is 2 [30], the
strength of any orientation is < 2. Therefore, this Hackett graph is fair (see
Section 3.3.3).
3.3.2 More Parameters
Definition 3.12 The disparity of a digraph G,
disp(G) = max s(Di) s{Df) 
D1UD2eO(G)
where 0(G) is the set of orientations of a graph G.
It is not very surprising to find that the disparity of some classes of graphs
go to infinity as the order of that class goes to infinity. However, in many cases
the function that bounds the disparity from above for a class of graphs is less
34
than linear as a function of order. A table of lower bounds of disparity for
various graphs and classes of graphs follows (in Chapter 7) and determines the
disparity for some graphs.
Definition 3.13 We say an irregular labeling of a digraph with mn vertices is
consecutive or sequential if the labels on the vertices form a rectangular lattice
in the space R x R.
Definition 3.14 We say an irregular labeling is perfectly irregular if it is con
secutive and it is an irregular slabeling.
Definition 3.15 The value sH is the minimum maximum value across all irreg
ular labelings such that an irregular labeling is defined by an arc labeling which
leaves the differences of inlabel and outlabel sums distinct.
3.3.3 Fairness and Cost
Definition 3.16 We define the irregularity cost of a digraph to be the minimum
area of a square in the xy plane that includes the coordinates of every vertex
weight of an irregularly labeled digraph.
Definition 3.17 A graph G is fair if disp(G) = 0.
Definition 3.18 A graph G is totally fair if s(D) = 1 over all orientations D
of G.
Now, in fact no simple graph except K\ and K> are such that every orien
tation is irregular. This fact amounts to the following Theorem.
35
Theorem 3.19 No graphs are totally fair except K\ and I\2.
Proof: We will show every graph except A2 and K\ has an orientation
with two vertices having the same outdegree, indegree pair.
Notice every graph has two vertices of the same degree with N(v)
[iV(u)] > 1 unless G = Ah or A'2.
So list the nodes of G left to right. If v = w exactly one neighbor of
v G {N[v) N[w]} is the unique vertex that follows v and w. If v ^ w list the
nodes of G left to right ,..., w,v so that w and v are last. Now orient the arcs of
G left to right.
That is, if 2 follows x in the queue orient the arc from x to 2: xz.
Notice that a necessary condition for a digraph to be irregular is that there
are at most k + 1 vertices of degree k in the underlying graph. Furthermore, it
is easy to see that if a sequence with exactly k + 1 vertices of degree k for all k
has a realization as a union of cliques which can be oriented so that s(D) = 1
in the resulting digraph D. Now, we can see there are no irregular orientations
of any bicliques except Ah,2 and A'i.i In fact, the only irregular oriented trees
are paths.
36
4. The Parameter A
The parameter A is a useful parameter in establishing the irregularity
strength of a digraph. Knowing A can prevent attempts to irregularly label
a digraph in a fashion that is clearly impossible (with too few labels available).
4.1 The Parameter A
Theorem 4.1 ([18]) Let D be a digraph and let U C V(D) be such that for all
x in U, ix < d+(x) < i2 and j\ < d~(x) < j2. Then
s(D) > max {s : qu{s) = 0}
UCV(D)
where qv(s) = (si2 i\ + 1 ){sj2 Ji + 1) \U\.
Proof: Let D be a digraph with irregularity strength s. Then the degree
of every vertex x in U must have i\ < d+(x) < i2 and jx < d~(x) < j2. It
follows that every vertex in U must have its weighted outdegree (indegree)
between L and si2 (j\ and sj2). We necessarily have that for all U C V(D),
(si2 /1 + 1)(sj2 ]y + 1) > \U\. Because this is the case for all such subsets
U C V(D). the theorem follows as stated above.
Definition 4.2 ([18]) Define A to be the largest zero of qu for a given graph.
The following corollary demonstrates the utility of this theorem.
Corollary 4.3 ([18]) Let D be an arbitrary rregular digraph of order \D\ = n.
Then (sr r + l)2 > n. Consequently, s> [ r~l + 1"].
37
Corollary 4.4 ([18]) Let D be an arbitrary digraph with k vertices of degree
(1,1). Then s> ~ y/k ].
Proof: Let s be the irregularity strength of D. Apply Theorem 4.1 with
U = the set of vertices of degree (1,1). We get s2 > k and so s > [ y/k ].
Corollary 4.5 ([18]) Let D be an arbitrary union of directed cycles with size
n; then s(D) > [ y/ri ]. Let D be a union oft directed paths with orders ki,
k2,...,kt: then s(D) > max{f, [ yjYnZ\(ki ~ 2) 11
Proof: For (J Cfc.. apply the previous corollary with U = V(D). For
(jPfcji consider three different applications of Theorem 4.1. Let U be the set of
vertices of outdegree 0, indegree 0, and degree (1,1), respectively. Since there
are t, vertices of outdegree 0, t vertices of indegree 0, and 2) vertices
of degree (1,1), the corollary follows.
The parameter A is not accurate up to a constant in all cases. There is at
least one family of disconnected graphs, , such that there does not exist
c G Z+ that gives s(Gn) < A(Gn) I c for all n Â£ Z+. (See Chapter 8 for an
example of such a family Gn.)
4.2 Minimizing and Maximizing A
The form of the polynomial that determines A suggests that regular and
nearregular orientations of graphs G will yield the smallest values of A. Given
a polynomial of the form ax2 + bx + c = \U\, the polynomial will have minimal
values when it factors if the two factors are nearly equal to one another. That is
if xy = \U\, minimizing max{.x, y}, is accomplished when x = cy has c 11 < e
for the smallest e possible.
38
Maximizing A is usually accomplished by finding an orientation of a given
graph with a large vertex set of sources or sinks, or a vertex set with large
indegree and small outdegree or vice versa. To see this, consider the equality
(AiA + 1) x (A2A <52 + 1) = \U\. The largest root is maximized when
one factor in xy = \U\ is much smaller than the other. Because the sum of
the indegrees equals the sum of the outdegrees, we get extremal examples for
connected graphs like the outdirected star. All this said, given a path with
several vertices of 0 in or 0 outdegree, and many vertices of degree (1,1), it is
possible that the vertex set that includes all the vertices of degree (1,1) produces
A.
4.3 Discussion
There are situations where regular orientations of a graph G do not yield the
smallest value of A over all orientations of G. Consider, for instance a transitive
tournament. While the transitive tournament is the only irregular orientation
of the tournament and has irregularity strength equal to 1, a regular orientation
of a tournament has A = s = 2.
Example 4.6 Consider the transitive tournament T2n+1 Consider also a regu
lar tournament on 2n + 1 vertices D2n+\ Clearly s(T2n+1) = 1 while s{D2n+\) =
2. But notice X(kf2n+1) = k while X{kD2n+i) = "VMkM" and we have
j v/fcrHfc11 < h as long as n < A;3 2k2 + k.
Also, given a graph that already has a nearirregular degree sequence, there
may exist an orientation of strength 1 if we allow sources and sinks, but no such
irregular orientation if we require every vertex has at least 1 in and 1 outdegree.
We consider irregular orientations of 2irregular graphs in Chapter 9. Given two
39
copies of an irregular graph, we can often show the irregularity strength is 2 by
simply multiplying the arc multiplicity of one of the copies by 2 on every arc. In
general, irregular labelings of digraphs is the study of spreading out clumps in
the degree sequence so that this spreading process does not cause the clumps to
then overlap. The parameter A gives us a bestcase scenario of how this might
occur.
Example 4.7 Given a regular digraph whose underlying graph is 2 colorable, we
can often take two copies of the underlying graph orient them differently to form.
D\ U D2 and get s{D\ U D2) = max{(s(Di), ^(ZA?)}. We give three examples:
D\ U D2
{D\ a diregular K>n2n Do a K2n^2n where one partite set beats the other)
Di U D2 C2n U G2n
(G2n is the anticycle on 2n vertices)
Di U D2 = C4 x CA U G
(G = C4 x C4 with an orientation where 1 partite set beats the other).
Consider a final example of this degreesequence clumping. Take a C3 and
expand each of the vertices to sets of orders k, 2k, 4k respectively. This gives an
orientation of the complete 3partite graph Kk.2k,4k Here, A(D) is 2. This may
not be immediately clear, but given two labels we can expand the three partite
sets degree sets so that they do not overlap and in fact do not collide.
One of the shortcomings of the paramater A is that we may have to check
many degree sets to determine A. However, we can see that. A is always bounded
40
below by
\A(D)
where n is the order of D. Here en is as defined in Theorem 3.5.
4.4 Disparity
A sufficiently large strength for one orientation of a graph is not enough
to guarantee disp(G) > 0. The obvious counterexample is the matching nl\2
However, given an outdirected star forest D whose roots are of sufficiently large
degree, and thus s(D) is large, has disp(D) > 0 where D is the graph underlying
D. Similar claims seem difficult to prove; it is difficult to prove bounds on smax,
and difficult to prove bounds on smin. In, fact we have few upper bounds on
the strength of a digraph unless there is a sufficiently large S. We can state if
S(G) > then s(G) <  + 1. but little else.
Given a set of vertices of cardinality U(G), of maximum degree k, we know
that at most ^ of these vertices are independent. Using this fact we can design
a chromatictype orientation that gives us that s(G) > If furthermore,
we have a 3regular graph with a Hamiltonian cycle (see Chapter 7), we can use
the congruence method to conclude that disp(G) > 1 1 Furthermore,
we have the following theorem:
Theorem 4.8 If G is kregular and has a Hamiltonian cycle, then disp(G) >
iTtbMi
41
5. The Complete Graph and Tournaments
In this chapter we outline a constructive result on the topic of digraph irreg
ularity strength. For now, we focus on establishing constructive results which
completely determine the irregularity strength of some families of digraphs. The
tournament is in a sense, the family of digraphs whose irregularity strength is
the easiest to determine among all families of digraphs which are completely
general. In fact the labeling is analogous to the labeling for the graph Kn. In all
cases except when Tn is transitive, the tournament Tn has irregularity strength
2 and in all cases except when the tournament is transitive (or when n < 3), the
same labeling algorithm applies. In the exceptional transitive case, the digraph
irregularity strength of our digraph Tn has s(Tn) 1. The transitive tourna
ments are the only digraphs whose underlying graph is regular and which have
irregularity strength 1.
5.1 sH(Tn) : A different definition for irregularity strength of
digraphs
The next two definitions will be helpful in Chapters 5 and 6.
Definition 5.1 ([30]) Define the deficiency of a vertex v to be def(u) =
deg+(v) deg~(v). Then denote the difference m the weighted outdegree and
the weighted indegree relative to an arc labeling by def/(r). We will commonly
write simply def(u) relative to an arc labeling especially when we are using the
def(r) relative to an arclabeling that, will be altered later in a proof.
42
Definition 5.2 ([30]) We define an arc labeling f as before. Then a Hackett
irregular labeling of a. digraph is an arc labeling such that the deficiency of every
vertex is distinct. The Hackettirregularity strength is denoted sH (D) and is
the minimum maximum label used across all Hackettirregular labelings of the
digraph D.
The number of arclabels required to arclabel a given tournament so that
the resulting multidigraph has every vertex of distinct deficiency is 2 [30], Notice
then that 2 is an upper bound for the irregularity strength under the definition
we use.
5.2 Tournament Algorithm: s(Tn)
In this section, we determine and prove the irregularity strength of every
tournament T.
Theorem 5.3 ([18]) The irregularity strength of a tournament T is 1 if T is
transitive and 2 otherwise.
Proof: Any transitive tournament is irregular and thus has irregularity
strength 1. As such, we let Tn be a nontransitive tournament of order n and
show that the irregularity strength of Tn is 2. The fact that S(Tn) > 2 follows
immediately from the fact that Tn is not irregular.
The only nontransitive tournament of order 3 is a directed cycle, which
clearly has irregularity strength 2. Suppose therefore that n > 4. Since Tn is
not transitive, there are distinct vertices z\ and z2 in Vr(Tn) such that deg{z\) =
deg(z2). Let the remaining vertices of Tn, listed arbitrarily, be 23,..., zn.
43
We now give an arclabeling of Tn with the set {1,2}. If i is even and j < i
let the arc between z, and Zj be labeled with a 2. Otherwise, label the arc with
a 1. Let w(zj) denote the sum of the inweight and outweight of zj. Then
3rt72
)
3n+j5
*)
j is odd and n is odd,
j is even and n is odd,
w(Zj) = <
:in i 1 j is odd and n is even,
3rvti~l j js even and n is even.
V 1
Note that w;(z;) ^ w(zj) except in the case that 7 = 1 and j = 2. Suppose
then that zi and z2 do not have distinct vertex weights. Then deg+(z\) =
deg+(z2) and deg~{z\) = deg~{z2). Represent the unweighted degree pairs of
Z\ and z2 by (n k, k) and (n k', k') respectively. Then the next equality
follows 2(n k j) + j = 2(n k' j') + j' and the value on both sides of
the equality is the weighted outdegree of and z2 (where here j and j are the
number of vertices indexed by odd numbers wThich are dominated by z\ and z2
respectively). Next, the equality 2(k h)+h = 2(k' h') + h' equals the weighted
indegree of z\ and z2 follows. Here, h and h' are the number of vertices indexed
by odd numbers which dominate Z\ and z2 respectively. Considering these two
equations together yields 4k = 4k! or rather k = kthat is, as claimed, the
vertices z, and z2 agree in unweighted degree if they agree in weighted degree.
Since (deg+(zi), deg~(zi)) = (deg+(z2). deg~(z2)), it is not difficult to show that
44
1
1
21
A
i
21
%
y*
*x yf
1
+x
l
2
Figure 5.1: Two cases in the final step of the tournament algorithm
Zi and z2 must lie on a directed C3 in Tn. Let x be the other vertex on this
directed 6:j and select a fourth vertex y in Tn so that for one of Z\ and z2, say z,
one of x and y dominates or is dominated by z wdiile z dominates or is dominated
by the other. We guarantee the existence of such a vertex y because otherwise
without loss of generality z\ wins only once while z2 loses only once. This last
eventuality is prohibited since n > 4 and if n > 4. no two vertices can have the
same degree under the above conditions. Now, perform the initial indexing so
that one of x and y has edges labeled 2 going to Zj and z2 and one has edges
labeled 1 adjacent with zi and z2. Then there are only two possibilities for the
orientations of these edges up to arc reversal, as given in the Figure 5.1.
If we switch the indices of x = z, and y = z:j to y = Zj and w = z^ we do not
change the total weight of any vertex with regard to the index of each vertex,
but we do alter the inweight and outweight of both z\ and z2. Under the
assumption that their quantities were equal under our prior ordering of V(Tn).
it is not difficult to see that they will be distinct after reordering.
The proof above can be generalized in various ways. We explore variations
of the general method here in Chapter 5 and additionally in Chapter 6.
45
5.2.1 Variations on the Algorithm
It is immediately clear that the tournament algorithm extends to semi
complete digraphs. We have previously defined semicomplete digraphs; we
have a single algorithm that determines a large portion of all digraphs. For the
sparser, oriented graphs, we have a completely different story; there does not
appear to be one simple construction that labels all oriented graphs.
Theorem 5.4 The strength of a semicomplete digraph SCn is one if its com
plement in the complete digraph Kn is irregular and 2 otherwise.
Proof: Let SCn be given. The proof given below is for n > 4. Notice
n = 2.3 can be done as exercises. Starting with the vertex of largest total degree
and ending with the vertex of smallest total degree, index the vertices for the
purpose of the labeling algorithm 2k. 2k2, 2k4...., k+2. k. k+1, A:+3,..., 2k1;
then pick an underlying tournament Tn C SCn and carry out the tournament
algorithm.
This gives two vertices of the same total weight and proceed to weight the
extra arcs with a 1 or a 2. Either choice of 1 or 2 for the extra arcs only stratifies
the vertex weights further unless there is a duplication from the tournament
algorithm. That is, denote the total weight of Zj under this first round of
labeling by w{zf) and obtain
46
3n i 2 + deg^Qn_Tn(zj) j is odd and n is odd,
3n+j5 __ deg^n_Tn(zj) j is even and n is odd.
U)(Zj) = <
3n 2J 1 + degtspn_Tn(zj) j is odd and n is even,
3n+j4 degg>l;n_Tri(Zj) j is even and n is even.
In fact, the indexing of the vertices assures that if
d^SscT(zj) ^ deggCn_Tn(zi)
then w'(zj) < w'(zi) where w' is the total weight of a vertex in Tn. That is, if
Vj has a larger total weight than in our labeled Tn. then necessarily has
a greater total weight than Vj after all the arcs in A(SCn) A(Tn) are labeled
with either a 1 or a 2.
Either the two vertices z\ and z2 have different total degree pairs or they are
the only two vertices with the same total weight after we label the extra arcs.
Suppose the vertices have the same total weight and the weighted degree pairs
match. Then the vertices z\ and z2 lie on a directed triangle in Tn. As such,
they lie on a directed triangle with another vertex, v. Furthermore, either we
are in Case 1 and one of these two vertices, Zi, has an arc to and from another
vertex, zu or we are in Case 2 and the two matching vertices z} and z2 form
an oriented split graph G with the tournament formed by z\ and z2 taken with
the odd indexed vertices of SCn joined to the vertices with even indices. (Here,
invoke that n > 4.)
47
Case 1: Label the extra arcs with a 1 or 2 depending upon which choice
gives either z\ or z2 a 2loop with some Zi such that the 2 arcs in the 2loop are
labeled with a 1 and a 2 respectively. In this case, if the (outweight, inweight)
pairs of z\ and z2 match after labeling the extra arcs a 1 and a 2. switch the
arc labels on z{Zj and zfzi without loss of generality. (So that for instance if the
label on ziz\ is a 1 and z{Zi is a 2, then after the switch ziz\ is labeled with a 2
and z[Zi is labeled with a 1.)
This maintains that there is only one tie in total weight and the 12 switch
breaks the (outweight, inweight) tie between the total weight matched vertices
Zi and z2.
Case 2: There are subcases depending on the structure of SCn. The vertices
Z\ and z2 lie on a directed triangle with another vertex Z*. These two vertices z\
and z2 also lie on a triangle with another vertex (which is not directed), Zj. We
will permute the indices of Zi and Zj as before in Theorem 5.2 and this will lead
to an irregular labeling under the new permutation of indices.
Subcase 2.1: Neither z; nor Zj is incident a 2loop. Then if we permute Zi
and Zj, this breaks the tie between z\ and z2 and leaves all other vertices with
distinct total weights.
Subcase 2.2: Both Z; and Zj is incident a 2loop that contains a 1labeled
and a 2labeled arc. Permute the indices of Zi and Zj. If the new Zi is tied after
the permutation, swap the 1 and the 2 label. This breaks the tie. Then, likewise,
if the new Zj vertex is tied after the permutation, swap the 1 and the 2 label.
This breaks the tie.
48
Siibcase 2.3: The weight of 2i; w(zz) > w(zj) and Zi is incident a 2loop that
contains a 1labeled and a 2labeled arc, but Zj is not incident a 2loop. Permute
the index i to j, but rather than permuting j to i, permute every even index
less than i up by 2 and put Zj at index 4. Then the new zj (previously indexed
Zi) has a 2loop that can be used to swap labels and break a tie; meanwhile, 24
can only tie z}. m
5.2.2 Collections of Tournaments
In this section, we introduce a parameter called /7. We show that in all cases
?i %) < m(U, Ti).
Theorem 5.5 s(Ui=i < k + 1 where all the Ti have the same order.
Proof: Number the tournaments T\,T2,.... T and then label them accord
ing to the procedure in Theorem 5.1. Then, consider the sum of the in and
outweights, each 7) has consecutive vertex labels with (at most) one repeat.
If n is even the sums of the weights are
3n 4 3n 2 3n 2 3n 3n + 2 . 0 _
.,, ,...., 2n 3, 2n 2.
2 2 2 2 2
If n is odd the sums of the weights are
3n 5 3n 3 3n 3 3n 1 3n + 1
...., 2n 3.
2 2 2 2 2
In each case there are n 1 consecutive vertex labels. So operate on the
labels of Tk by k 1 (adding k 1) to each label, obtaining a sequence of
almost all distinct vertex weights where the duplications have distinct in and
outweights by our previous discussion. So all vertex weights are distinct with
n + 1 labels, so that s(D) < k + 1.
49
The following algorithm is also helpful for bounding the irregularity strength
of collections of tournaments from above.
Definition 5.6 Let U+ be the set of vertices of a digraph D such that deg+v > 0.
Definition 5.7 Let f/0 be the set of vertices of a digraph D such that deg+v 0.
Definition 5.8 Let A+ be the value we get as a maxim,urn, outarc label in the
labeling we get in the following way:
Rank the vertices ofU+ by outdegrees f : U+ > {1. 2, ...\U+\} is a bijection,
and then queue the arcs once by g so that
g {vifui :l
is a bijection (if the fbuilding encounters ties in outdegree, break those ties
arbitrarily).
Now the label on a^eg+Vj)+k where deg+Vj + 1 < k < deg+vj + deg+Vj+\ is
fV]+l
Definition 5.9 We say ft = X +(U+) + \Uq\.
Discussion: The parameter ft is an upper bound for s of a digraph D if the
following algorithm terminates.
i. Steps 1 through A+(U+).
Weight the outarcs of the digraph as described. This amounts to a com
pleted arclabeling though we can see it may not be irregular.
ii. Consider the bigraph [U+,Uq\.
50
iii. If the bigraph is acyclic the next step terminates in < [/0 steps, leaving us
with an irregular arc labeling that is an irregular p,labeling where // < p
and clearly A < s < p.
iv. Steps X+(U+) through A+(I/+) + f/0.
Rank the vertices in (/0 by h : Uq > 1, 2, ...Â£/0, sorting vk. below Vj if there
exists ar such that vk. ~ ar where for all t such that at ~ Vj, r < t
Then starting tie of greatest total weight in Uq after Steps iiii, then we
pick the lowest ranked arc a, incident the highest //ranked vertex in the
tie and add 1 to every label on every arc Oj j > i.
Supppose the algorithm cycles, that ties recur. There is no tie between
v, x U+ because if v is ranked higher by / than x no matter how many times
we iterate step iv. steps iiii guarantees v always has greater outdegree than x.
Suppose v G U+ and x G Uq. This is a contradiction since x has outdegree
0.
Suppose v,x Â£ U0. Then suppose h ranks v higher than x. we necessarily
have that every time t, inarcs incident v increase by 1, and more than t arcs
incident x increase by 1 due to the nature of h. Step iv breaks the tie between
v and x, and they can never retie.
It remains to calculate A+{U+).
5.2.3 Multipartite Digraphs
Theorem 5.10 The strength of Km(n) whose condensation is transitive is 2.
Proof: Let the partite sets be labeled l,...,m. Let the vertices be labeled
by an ordered pair of two subscripts, one for the partite set containing it and
51
one for a number between 1 and n. In this way order the vertices of each partite
set 1 through n and get mn vertices each with a unique subscript (h, k) where
h indicates a partite set and k indicates an element of the respective partite set.
If h < h' and k < k' the arc Vh.kVh'.k' is labeled with a 2, otherwise, label the
arc with a 1.
We get
w(vh,k) = {(nh)(k),(hl)(nk) + (nh)(nk)) = (k(nhl),(nk)(nl)).
Now suppose xu(vh,k) w(vh'.k) That is, suppose
(k(n h I), (n k)(n 1)) = (k'(n h' 1), (n k')(n 1)).
Then k k' by consideration of the second arguments in the equality. And,
using that k = k' and the first arguments of the equality it follows h = h'. That,
is the labeling is irregular.
There are a number of general constructions based on building irregular
labelings from other irregular labelings.
Theorem 5.11 Given an irregular slabeling of a graph G, if we replace each
vertex in G by an arbitrary (not necessarily identical) tournament of order n,
then the strength of the resulting digraph is necessarily < 2s. If all the tourna
ments are transitive, we can lower the bound to s.
Proof: Suppose the tournaments are of equal size. Then, (*), if we weight
the tournament according to our tournament algorithm, the tournament image
of each point v has minimum total weight 2w(v) + 1 and maximum total weight
2w(v)n+2(n l), where 2w(v) is twice the weighted degree of v in our irregularly
52
labeled G. Then as long as the points in G are separated by 1, and we multiply
the arcs by a factor of 2, the algorithm (*) amounts to an irregular labeling of
the new digraph D. So, given an irregular slabeling that separates points by 1
integer, multiply ever} edge label by 2. This gives us a greatest label of 2s. If
the tournaments are all transitive, we do not have to separate the points by 2
to begin with.
Theorem 5.12 Given an irregular slabeling of a digraph, if we replace each
vertex by an arbitrary (not necessarily identical) tournament of order n, then
the strength of the resulting digraph is necessarily < 2s. If all the tournaments
are transitive, we can lower the bound to s.
Proof: Suppose we replace, vertices of digraph D with tournaments of
different size and replace the arcs with tournament joins. If vertex v associated
with tournament Tv has different weighted degree in the irregular weighting of
D than vertex x, then every vertex in Tx has different weighted degree from
every vertex in Tv. Suppose the outdegrees agree on 2 of these vertices. Then
the indegrees do not: for 2nw~(v) I 2(n 1) < 2n(w~(v) + 1).
Theorem 5.13 If we replace every vertex of a directed cycle with a directed
cycle; i.e., take the directed cross product of a cycle iteratively, then D = Y[\i!{Cn,
and s(D) < \y/ri ]fc
Proof: Iteratively, multiply the weight of the arcs of the digraph being
expanded by " sfh ]. Then weight each vertex of the cycles replacing the vertices
with the weight of the root vertex plus the weight given by an irregular labeling
53
of the cycle. Again, if the outdegrees of two points agree, the indegrees do not
\y/n]u~(v) + \y/n ] < (\y/n l((u) + 1)) + 1.
54
6. Small Irregularity Strength
6.1 s = 2, and disp = 1
First we cite [30] and rewrite some theorems. Notice some of the results
wrere actually proved in [28] and [16].
Theorem 6.1 ([30]) Let G be a graph such that s(G) = 2 and f/(G) = n.
Then Â£'(G') > Fr n=3 mod 4, Â£'(G') > + 1. Furthermore,
there exist graphs H for which equality holds.
Theorem 6.2 ([30]) Let G be a graph such that l/(G') = and s(G) = 2. Then
Â£(G) < sji.
Theorem 6.3 ([30]) Let m, n and a be fixed positive integers with 2m < n <
4a + 1 and let M be a fixed melement subset of the vertex set of Kn. If G is a
graph obtained from Kn by deleting a edges of the complete subgraph induced by
M, then s(G) = 2.
Theorem 6.4 ([30]) If G has () edges and the complement of G is
not a matching, then s(G) = 2.
Theorem 6.5 ([30]) If G is a graph obtained from Kn by deleting a edges,
< a < % 1. such that the removed edges induce a connected graph, then
s(G) = 2.
Theorem 6.6 ([30]) If G=Kn Km and 2m < n < 2rn2 2m + 1, then
s(G) = 2.
55
Definition 6.7 A split graph SPp,q has an independent set of size p joined to a
clique of size q. We call a split graph SPM a Type 1 graph if p = q2 q.
Definition 6.8 A graph Kn Kp q is called a cloister. A cloister with p + q =
[\/n\ is called a Type 2 graph.
Theorem 6.9 (i) Type 1 and Type 2 graphs have graph irregularity strength 2;
(ii) Type 1 arid Type 2 graphs have disparity 1.
Proof: By previous work [30] Type 1 and Type 2 graphs have graph irreg
ularity strength 2. Notice it follows they necessarily have digraph irregularity
strength < 2 for all orientations. If we take a transitive tournament of the same
order as our Type 1 or Type 2 graph and remove either (1) a clique formed by
the vertices l,p, 2p, ...,p2 or (2) a biclique all of whose vertices in one partite
set are ranked above all our vertices in the other partite set we get an irregular
digraph whose underlying graph is our desired Type 1 graph or Type 2 graph.
By the characterization of totally fair graphs, it follows that Type 1 and Type
2 graphs have disparity equal to 1.
6.2 If n > 1, s(Kn,n) = 2
The study of irregular labelings for digraphs actually began in [30], where it
was required that two vertices have distinct deficiency for their weighted degrees
to be distinct. We will use the definition of the deficiency of a vertex as well
as the following lemmas in order to show Kn.n is fair for all values of n. In the
following discussion / is an arclabeling, and g(v) = ([h + def/],ic/) where here
def/(u) is = Â£) f(vx) ~ E /(^;) and wf(v) = E f(vx) + Â£ f(xv).
56
Definition 6.10 A (0, l )labeling of a digraph D is a subdigraph D C D where
the arcs labeled 1 are in A(D) and the arcs labeled 0 are not in A(D).
Definition 6.11 An irregular (0,1)labeling of a digraph D is an irregular sub
digraph, D C D whose arcs are labeled 1 and all arcs of D D are labeled 0.
Definition 6.12 An irregular (0,1)labeling of a digraph that does not use ver
tex weight g{v) = (0, 0) is called a (0, IS)avoiding irregular (0,1)labeling. Mean
while, an arc labeling of a digraph that does not use vertex weight g(v) = (0, 0)
is called a (0,0)avoiding labeling.
Theorem 6.13 For n = 3, every orientation of Kn n has an (0,0)avoiding
irregular (0,1)labeling.
Proof: Consider the feedback graphs of size 1,2,3,4. There are two graphs
of size 2; there are four graphs of size 3; and three graphs of size 4. In each
case, the feedback graph gives rise to an irregular (0, l)labeling. In some cases,
the placement of the feedback digraph, i.e., which vertices are in which partite
set, is important to consider. See Appendix A for proof by cases. These picture
proofs label the digraph irregularly using the following function / for labeling.
The function / labels the arc between and vjb with a 1 if i + j > 3 and
0label otherwise. The labeling is complete once the permutation of the vertex
set is established.
Definition 6.14 Let an orientation of Kn n, called D be given. A function h :
V(D) Z is called a feasible initial condition in the (0, 0)avoiding case unless
D is oriented so that team A beats team B, H\a = d, h\s = c and c, dÂ£ (2, 2n).
57
Theorem 6.15 Every orientation of C4 with every feasible initial condition has
an (QA))avoiding irregular (0,1 )labeling with the following two exceptions:
i. the digraph {(rl/iii#), (viBv2A), ('V2ax2b), (*2b^ia)} with the initial condi
tion h(v1A) = h(v2A) = h{vlB) = h{v2B) = c.
ii. the digraph {(viaOib), (viBA2A), {v\aV2b), {v2Bv2a)} with the initial condi
tion h(vL4) = c, h(v2A) = c + 6, h(vlB) = c + 4, h(v2B) = c + 2.
In most applications of 6.15, we will use that the C4 in question is a sub
digraph of some superdigraph D and that there is a function h (which will be
feasible by Lemma 6.20) imposed on the C\ by the arcs from the C4 to D C4.
Proof: The proof is by cases, see Appendix A for an explanation of how
the proof works.
Lemma 6.16 Let h : V(Kz$) be a feasible initial condition on an orientation of
A'3.3, called K3 3. If the leave of a double star {xviB,xv2B,xy,yi'iA, yv2A} where
h(x) ^ h(y), is one of the exceptional graphs (i.) or (ii.) from 6.15, then without
loss of generality h(x) 7^ h(v\B), and the leave of{xviB, xv2B, xy,V\BViA,v\Bv2A\
is not (i.) or (ii.).
Proof: Case 1: If we have exceptional graph (i.) or (ii.) under forbidden
conditions and we permute y and v\B and get the same exceptional graph under
forbidden conditions, then selecting v2B (and permuting it with y) necessarily
gives the other exceptional graph under nonforbidden feasible initial conditions
except when we are in Case 2. We get
[h, h, h, h] > [h, h, h, h'] ^ [h0, h0 + 4, h0 + 6, h0 + 2]
58
or
[ho, ho + 4, ho + 6, hg + 2] > [ho. ho + 4. ho + 6, h'} 7^ [h, h. h. h].
In the case that, permuting y and vlB does not return the same exceptional
graph under forbidden conditions, it returns the same graph under allowable
conditions, a graph different from the ones underlying (i.) and (ii.) or the other
forbidden graph under allowable conditions:
[/?o, ho + 4, h0 + 6, ho + 2] [ho, h/, ho 4 6, ho f 2] 7^ [h, h, h, h],
or
[h, h, h, h] [h, h h, h] 7^ [ho, ho + 4. ho + 6, ho + 2].
Case 2: In the exceptional case that h(x) = h(?;1B) or = h(u2B), and (i.)
or (ii.) is the leave, then under one of the following permutations we get a
nonforbidden leave as a subgraph:
[ho. ho + 4, ho + 6, ho + 2] [ho, ho + 4, ho + 6, ho + 4] 7^ [h, h, h, h]
7^ fa), ho + 4, ho + 6, ho + 2].
or under the permutation
[ho, ho + 4, ho + 6, ho + 2] [ho, ho + 2, ho + 6, ho + 2] 7^ [h, h, h. h]
7^ [ho ho + 4, ho + 6, ho + 2],
and we are done.
In the case that h(x) = h(vlB) = h(v2B), and (i.) is the leave, then we swap
via or v>a for x. Since h(ig^) = h(v[B) 7^ h(y) this permutation gives a leave
59
(3.3)
(4.2)
P
(3.3)
% '4'3>
1
(2.4)
(3,2) *
T /
ft (4.4)
1
(3,2)
 t (2.3) V (3.4)
' ./
! /' 2 1
! /
*%
(3,3) (42) (3,3)
Figure 6.1: A (0. 0)avoiding irregular (0, l)labeling of the Hamiltonian reg
ular orientation of gives rise to this irregular 2labeling of the same orientation
of Ah.4 pictured here on the torus.
which does not have one of the forbidden orientationinitial feasible condition
combinations. If the orientation changes to (ii.), the fact that
[h h, h, h] 7^ [h0, ho + 4, ho + 6, ho + 2]
completes the proof.
Theorem 6.17 For any diregular orientation of G' = A"n,ri with n > 2, there
is a (0,0)avoiding irregular (0,1 )labeling of G'.
Proof: Let AuB be the bipartition of V(G") in the discussion that follows.
Pick a vertex x G A from G'. Label x as V\a On the ordering of the vertices we
eventually select, label the arcs so that if
ViA^jB Â£ A(Ii.n,n) i 3
60
or if
VjBtiA ^ A(I\n,n) j+ i
then the arc is labeled with a 1; otherwise the arc is labeled with a 0. Continue
selecting vertices of G" in the following way and labeling the vertices viB,
for 1 < i < n 1 : pick d*# and up+pB so that they do not have the same
number of 0labeled victories. To see that this can always be done, consider the
graph G" = G {x^a, +/b 1 < k < i + 1, 0 < j < i}. Suppose for every pair
of vertices we select, one from each side of the partition, the two vertices have
the same number of 0labeled victories in G". Then G". whose underlying graph
is Km.m+i for some m, has degree sequence (a. 6)l, (a 1, b + (a 1, b)1'.
(a,b Since we cannot select a vertex of degree (a.b) that beats a
vertex of degree (a.b 1) nor a vertex of degree (o 1,6+ 1) that beats a
vertex of degree (a 1,6) by assumption, we must have that every vertex of
degree (a, 6) beats every vertex of degree (a 1, 6) beats every vertex of degree
(a 1, 6 + 1) beats every vertex of degree (a.b 1) beats every vertex of degree
(a, 6). But then we have a vertex of degree (a 1, 6+ 1) beats a vertex of degree
(a, 6 1) contrary to assumption. So we get that t = m, and the equations
t'(a 1) + (m + 1 t')a = mb
and
t'(b) + (m + 1 t')(b 1) = ma
follow. From the first equation we get a = 6. From the second equation we get
that t' + 6 = m + 1 or rather that t' = a = 6. But notice that since t = m and
m t = 0 we get a 1 = 0 and a = 1. The only way the selection process
61
can stop is if there are three unordered vertices, they are the last three in the
queue, and we get degrees (0,1). (1,1), (1,0) in G". In this case (*) order the
vertices so that the vertex of degree (1,0) is V(n^)B. the vertex of degree (1,1)
is vnA and the vertex of degree (0,1) is vnB. Label the arc t\n\)BVnA with a 1
and vnAvnB with a 0. Then g(vnA) = (0, n) and g(vnB) ^ g(v{n_i)B). However,
the total weight of t>(ni)B and vnB are identical to one another and distinct
from all other vertices of G'. In general, no two vertices v, w can have the same
weighted degree pair g(v) g(w) unless g(v) = (/', i") = g(w) = (/, j")
unless i' + i" = i = j = j' + j" where v 6 A and w e B and where i and j are
the number of vertices v and w dominate respectively. That is. unless v = viA
and w = t(i_i)B for i < n 1 these two vertices cannot have the same weighted
degree pair because of how we selected the vertices (in pairs) and because we
handled the one exception where this selection process is not followed precisely
(*). To see that there is a (0, 0)avoiding labeling, suppose beats vrb.
Then simply reorder the vertices so that kA <> (n k + 1)5; i.e.. flip the
construction upside down (rotate by 180 degrees).
Corollary 6.18 Every diregular orientation of K4A has a (0,0)avoiding irreg
ular (0,1)labeling.
Proof: The proof is by the above construction. (See the Figures 6.1 and
6.2.)
Definition 6.19 An A beats B tournament is an orientation of KniU where
every vertex in partite set A dominates every vertex in partite set B.
62
(2.4)
(3,3)
A
(2.4)
A (4'2)
C (3':
(2.3)
V (4,4)
A (2'3)
\ 2 2 \,2 1
( (4.3) A; (3.4)
,/2 \. ] /2 ''.2
rA
(2.4) (3,3) (2,4)
Figure 6.2: A (0, 0)avoiding irregular (0, l)labeling of one of the regular
orientations of /\4,4 gives rise to an irregular 2labeling of the same orientation
of A4 4 pictured here on the torus.
Lemma 6.20 Suppose h : V(D) 
Kn n (with n > 3). Then define h'
h'(v) = h(v) + 1
h'(v) = h(v) 1
h'(v) h(v) + 1
ti{v) = h(v) 1
Z is feasible where D is an orientation of
if vx Â£ A(Kn
if xv Â£ A(Kn%n)
if vy Â£ A(Kn,n)
if yv Â£ A(Kn:n).
where x and y are such that [h + defj (x) [h + def](y). Then if h' is not feasible
on D {x,y} it follows that D has a (0. 0)avoiding irregular (0,1 )labeling.
Proof: Suppose h, D. x, y meet the hypotheses of the theorem and that h'
(as defined above) is not feasible. Then there are four cases for the neighbor
hoods of x, y and we can show in each case that D has a (0, 0)avoiding irregular
63
(0. l)labeling. Since h' is not feasible we have by definition of feasible, that
D  ;//} is an A beats B tournament such that h\B h\A Â£ (2, 2n). Suppose
when we extend back to the digraph that x Â£ A and y Â£ B. Index x as v\a
and the rest of the vertices of A as v2A. ,vnA Index y as v\b and the rest of
the vertices of B as v2b vnB. For the purposes of the proof, let / be the arc
labeling that labels viAVjB with a 1 if i + j < n + 1 and labels ViaVjb with the
0label otherwise. Furthermore, under the current index and the labeling /, let
k' be the index which has [h + def](tV4) = [h + defj(iVB)
Case 1: Suppose B dominates x and y dominates A.
Case 1.1: Suppose k' > (n + 1). Suppose k' + 2 < n.
Case 1.1.1: Permuting 1A (kf + 1)^4 leads to (a) [h + defj^i^) = [h +
def](u(^+1)B), or (b) [fi + def](uiB) = [h + def](u(/t/+1)A).
Case 1.1.2: Permuting IB (k' + 1 )B leads to (c) [h + def](?;lyi) = [h +
def](u(fc'+i)s), or (d) [fi + def](tiB) = [h + def](u(fc/+1)A).
Notice there cannot be (a) and (c) : if (a), then [h + def](ui^) = hi under
the original ordering and [h + def](u(*./+i)) = h2 under the original ordering, then
hi + k = h2 and if (c). then h2 + k = h\, a contradiction. Meanwhile (b) and (d)
cannot occur together by similar reasoning.
Case 1.1.3: Permuting 1 < k + 2 leads to duplications: we have [h +
def](uly4) = hi under ordering in Case 1.1.1. And, [h + defj(uiB) = ho under the
ordering in Case 1.1.2. So under the ordering in Case 1.1.3, [h + def]^^) =
hi + 1 + t and [h + def](u1B) = h,2 1 t. If V\aVib A(D), then t = 1.
Because hi ^ h2, and because [h + def](t(fe/+2)/i) ^ [h + def](u(fc'+2)s) under this
new ordering, it follows this permutation of the order admits that / is a (0,0)
64
avoiding irregular (0. l)labeling of D. (It is clear [h + def\(vjA) ^ [h + def](vjB)
for j 7^ k' + 2 because we permuted both vXA and vXB to a tier with index
>Â£( + !))
Case 1.1.4: Suppose V\bvx.4 G A(D). Permute lA <> (k'+2)A and IB nB.
Then [h + def]^) = hx j [h + def]('U(fc/+2)B) under this ordering because
hi = [h +defj(t>(fc/+1)B) under this ordering. It is also clear that [h + def](uiB) 7^
[h + def](un^) under this ordering by similar reasoning as long as n > 4. If n = 4
on the other hand, then k' = 2 and k > 2, a contradiction. This concludes Case
1.1.
Case 1.2: Suppose k' >  (n +1). Suppose k' + 2 > n. Permute 1 <* k' + 1.
Then [h + def](rM) = hi +1 and [h + def](?;iB) = h2 t. Because hi = h2, this
concludes the Case 1.2.
Case 1.3: Suppose n = k' > (n + 1).
Case 1.3.1: Permuting 1A < k'A leads to (a) [h + def](ti^) = [h + def](tyÂ£),
or (b) [h + def](uiB) = [h + def^ty,*).
Case 1.3.2: Permuting IB <> k/B leads to (c) [h + def](uL4) = [h + def](tyB),
or (d) [h + def](uiB) = [h + def)(ty.4).
Case 1.3.3: Permuting 1 k' leads to a duplication. Let [h + def^ui^) = hx
under ordering in Case 1.1.1. And. [h + defj(uig) = h2 under the ordering in
Case 1.1.2. So under the ordering in Case 1.1.3, [h + def](t^ia) = hi + 1 + t
and [h + def](ui#) = h2 1 t. If vxAVib G A(D), then t 1 and because
hi = h2, and because [h + def](ty.4) 7^ [h + def](ty.e) under this ordering, it
follows this permutation of the order admits that / is a (0, 0)avoiding irregular
(0, l)labeling of D. (It is clear [h + def^u^) 7^ [h + def](t;y)B) for j 7^ k' + 2
65
because we permuted both vlA and vXB to a tier with index > (n + 1).)
Case 1.3.4: Suppose vxB1)M e A(D) (and so t = 1). Permute 1A k'A,
15 <> (k1 1)5. As long as k' = n > 2, it follows that this will not lead to
a duplication because Vi^ib is labeled with a 0label under this ordering and
the condition 3 < k'. So then [h + def](r:lj4) = hi + 1 ^ hi = [h + def](ufc/B).
Furthermore, [h + def](?;iB) = h2 ^ h2 + 1 = [h + def]^^!)^). Finally, the 2
vertices permuted to the top tier do not fix [h. + def]. This concludes case 1.3.
Case 1.4: Suppose k' < A 1).
Case 1.4.1: Permuting 1A k'A leads to (a) [h + def](ui^) = [h + defj {vk>B).
or (b) [h + def](viB) = [h + def](^.^).
Case 1.4.2: Permuting 15 k'B leads to (c) [/?. + def](ui^) = [/?. + def](ufc/B),
or (d) [h + def](u1B) = [h + def](ufcM)
Notice there cannot be (a) and (c) : if (a), then [h + def](rqyi) = hi under
the original ordering and [/?. + def](vv/i) = h2 under the original ordering, then
hi Ak = h2 and if (c), then h2 + k = hi, a contradiction. Meanwhile (b) and (d)
cannot occur together by similar reasoning.
Case 1.4.3: If we permute 1 k', we get a duplicated vertex pair. Suppose
then [h + def](ni^) = hi +t= [h + def](uiB) = h2 t, under this ordering; ie.
define t in this fashion.
Case 1.4.4: Permuting 1A > k'A, 15 nB leads to a duplication. Then
[h + def](uM) = hi + t ^ [h + def](tvn) where t equals +1 or 1 (depending
on the arc direction between viA and V\b) under this ordering because h\ =
[h + def](ufc/B) under the ordering 1.2.1. If [h + def](uiB) = [h + def](un^) = hn,
then h2 k = hn for nonzero k unless k' = n, contradiction.
66
Case 1.4.5: Permuting L4 nA. IB +> k'B permits a duplication. Then
[/i + def](^iB) = hxt 7^ [h + deÂ£(tvu) where t equals +1 or1 (depending on the
arc direction between vXA and vXB) under this ordering. Now h2 = [h + deÂ£](iV/i)
under the ordering 1.4.4. If [h + def](uis) = [/i + def](tv4) = hn. then hi + k = hn
for nonzero k unless k' = n, contradiction. But hx = h2 21. So hi + 2k = h2
so that t, = k = 1. But then k' = 2, n = 3.
Case 1.4.6: k' = 2. n = 3 and Cases 1.2.11.2.5 fail to resolve duplications.
Permute 1 n. Then hx + 2 ^ h2 2, so that [h + def^u^) ^ [h + def](uiÂ£)
under this ordering. Furthermore [h + def] (t'fc/J4) ^ [h + def](ufc/B). This can be
seen in 2 ways: (1) we permuted 1 n, (2) hx 1 ^ h2 +1 = hi + 2 +1 = hi + 3.
This concludes Case 1.4, and therefore concludes Case 1.
Case 2: In this case suppose x is dominated by B. but y dominates some of
A and is dominated by some of A.
Permute vXB and vnA maintaining that v^<+\)a beats vXB and vxB beats v^a
Case 3: In this case suppose x is dominated by some of B and dominates
some of B. Meanwhile, y is dominated by some of A and dominates some of A.
Permute vXA and vnB maintaining that v^'+X)B beats vXA and vXA beats Vk>B
Case 4: In this case x dominates A and y is dominated by B.
Case 4.1: Suppose x beats y. Permute vXA and vXB with ivu and v^b
Case 4.2: Suppose y beats x.
Case 4.2.1: Suppose k! > \{n+ 1).
Case 4.2.1.1: Permuting 1A <* (inax{n, /d+l})A leads to (a) [h+defj^i/i) =
[h + def](u(fc/+i)B), or (b) [h + def](uiB) = [h + def](t(fc/+i)j4).
67
Case 4.2.1.2: Permuting IB (max{n, k'+l})B leads to (c) [7?def](^ia) =
[h + def](u(fc/+1)B), or (d) [h + def](u1B) = [h + def](i;(fc/+1M).
Notice there cannot be (a) and (c) : if (a), then [h + def]= hi under
the original ordering and [h + def](u(fc/+1)) = h2 under the original ordering, then
h\ + k h2 and if (c). then h2 + k = hi, a contradiction. Meanwhile (b) and (d)
cannot occur together by similar reasoning.
Case 4.2.1.3: Permute 1 <> maxjrc, k' + 2}. Then [h + def](?;L4) = hi under
ordering in Case 4.2.1.1. And, [h + def](uiB) = h2 under the ordering in Case
4.2.1.2. So under the ordering in Case 4.2.1.3, [h + defKu^) = hi + 1 + t
and [h + def](n1B) = h2 1 t. If UiTfis A(D), then t = 1. Because
hi = h2, and [h + def](u(fc/+2).4) 7^ [h + def](u(fe/+2)s) under this ordering, it
follows this permutation of the order admits that / is a (0,0)avoiding irregular
(0, l)labeling of D. (It is clear [h + def]^^) 7^ [h + def](ujB) for j 7^ k' + 2
because we permuted both Via and Vib to a tier with index > (n + 1).) This
holds as long as k' + 2 < n.
Case 4.2.1.4: Suppose VibVia Â£ A(D) (and so t = 1). Permute 1A k'A,
IB (k' \)B. As long as k' = n > 2, it follows that this will not lead to
a duplication because ViaVib is labeled with a 0label under this ordering and
the condition 3 < k'. So then [h + def](ui^) = hi + 1 ^ hi = [h + def^tve).
Furthermore, [h + defKujs) = h2 7^ h2 + 1 = [h + def](v(/t'_i)J4). Finally, the two
vertices permuted to the top tier do fix [h + def].
Case 4.2.1.5: Suppose k' + 2 > n. Permute 1 *+ max{n,k' + 1}. Suppose
k' + 1 < n. It still follows that hi 1 7^ h2 + 1, so that [h + defj^i^) 7^
[h + def](niij). Furthermore, it is clear that no vertices from any other tiers have
68
9(vja) g{vjB).
Case 4.2.1.6: If k' + 1 > n, then permute 1A < k'.
Case 4.2.1.6.1: Permuting L4 <> k'A leads to (a) [h + defj^y^) = [h +
def](?vB), or (b) [h + def](u1B) = [h + def](vfeM).
Case 4.2.1.6.2: Permuting IB k'B leads to (c) [h + defj((;lj4) = [h +
def](ufc/B), or (d) [ft + def(uiB) = [h + def](?;fcM).
Notice there cannot be (a) and (c) : If (a), then [h + def](ui^) = hi under
the original ordering and [h + defjfhvu) = ho under the original ordering, then
h\ + k = ho and if (c), then h2 + k = hi, a contradiction. Meanwhile (b) and id)
cannot occur together by similar reasoning.
Case 4.2.1.6.3: Permute 1 <* k'\ We have [h + def](cp ^) = hi under ordering
in Case 4.2.1.6.1. And, [h + def](riB) = h2 under the ordering in Case 4.2.1.6.2.
So under the ordering in Case 4.2.1.6.3, [h+defKwi^) = hi+t and [h+def](r?iB) =
h2 t. For, in any case, either ViaVib or V\bI'\a Â£ .4(D), so t > 0 and because
hi = h2, and because [h + defjtyv^) ^ [h + de(\(vkB) under this ordering, it
follows this permutation of the order admits that, / is a (0, 0)avoiding irregular
(0, l)labeling of D. (It is clear [h + def(u^) ^ [h + def](tjB) for j ^ 1 under
this order because k! was the tier with duplications.)
Definition 6.21 An (n)avoiding (0,1)labeling of D where D is an orientation
of Kn n is a (0, 0)avoiding irregular (0,1 )labeling on D {x,y} where x and y
come from opposite partite sets.
Lemma 6.22 Suppose h : V(D) Z is feasible where D is an orientation
of Kn n (with n > 3). Then if h is not feasible on D {x,y} it follows that
69
D {x,y} is feasible for some other choice of x and y such that h(x) ^ h(y).
Proof: Let A U B be the bipartition of the vertex set of D. If D {x, y} is
not feasible, then Ii\a(D) ^ h\rj(D). Pick any vertices from A {x} and B {y}
respectively (unless one of the vertices is incident with a unique feedback arc in
which case, do not pick the other endpoint of that arc). The remaining graph
is feasible. For. without loss of generality, either h(x) ^ h\A or x is incident a
feedback arc.
Theorem 6.23 Every orientation of K4A has a (0,0)avoiding irregular (0,1)
labeling.
Proof: The orientation K4A is not regular, so assign a double star
xv4,xv5.xvQ,xy.yvi1yv2,yv3 such that def(x) ^ def(y) and label all its arcs with
1. Let /L33 be the digraph induced by V(K4A) {x.y}. Either there is a pair
of vertices v and w such that \h' + defc'/c3 3](?;) 7^ W + def(7>_A3 3](w) where
h'(v) = h(v) + 1
h' (v) = h(v) 1
h'(v) = h(v) + 1
h'(v) = h(v) 1
if vx G A(Kn.n)
if xv G A (I\n jx)
if vy G A(Kn,n)
if yv G A(kn,n)
or the labeling /' = 1/ on the arcs A'3i3 completes the labeling; that is, if f* = 1
on G" = G1 A"3 3 and /* = /' on A'3j3, then /* is a (0,0)avoiding irregular
(0, l)labeling. (Here, h' is feasible or we can label the digraph completely by
Lemma 6.20.) For consider, the vertex weights of x and y are n and larger
than any other vertex in the labeled digraph. But [h + clef] (,r) ^ [h + def](y).
70
(From this comment it should be clear the labeling is (0, 0)avoiding.) Then /*
is distinct on A'3.3 by definition of h' and /'. The function / is given by Theorem
6.13. In the case [/;/ + defc'/ju 7^ [/?/ + def<2"]iu, it is clear that there is a way to
complete the arclabeling so that it will be irregular, by induction from Theorem
6.15, and Lemmas 6.16, and 6.22. We have h'(v) 7^ h'(w) for some choice of v
and w that leaves us with a C'i under conditions for which there exists a (0,0)
avoiding irregular (0, l)labeling, call it /. Let f* = f on G'" = G" {u,u'}.
Then f* = 0 on G" G"' and 1 on G' G". So then [fidef/.](t>) 7^ [/?,+def/](u)
and clearly f* is a (0, 0)avoiding irregular (0, l)labeling.
Lemma 6.24 Let n > 3 and let an orientation of Kn,n, G' = Kn_n, with a
feasible initial condition h such that [h + def](x) 7^ [h + def] (2/) for x and y in
V{Knjn) be given. Then there are two possibilities. The first possibility (i) is the
following. The orientation Kn n is a team tournament where team A beats team
B and [/i + def](ar) is constant for x in partite set A under the labeling fi(af) = 1
for all ai G A(Kn^n). Also, [h + defj(y) is fixed for all y in partite set B under
the same arc labeling and h(x) = h(y) 2(n 1). The other possibility (it) is we
can find some pair of vertices which we call x and y such that h(x) 7^ h(y) and
[h + def(7'_{a,,y}](n) is not fixed over the remainder of the vertex set when we cut
vertices x and y, he., not fixed over V(Kn%n) {x.y}.
Proof: Let G' = Kn,n and h meet the conditions of the theorem. Let
A U B be the bipartition of V'r(Kn.n) We want to show if case (ii) does not hold,
case (i) holds. Suppose for all choices of x,y where h(x) 7^ h(y), we get a fixed
value for [h + defG'{.T,y}](?0 for v G V(Kn.n). If there is a fixed h value on V\a
71
every distinct h value on V\ b is associated with a unique neighborhood. To
prove this last assertion observe that it cannot be the case that h(x) = h(z)
and (N+(z),N~(z)) ^ (7V+(x), N~(x)) for ^ e V(G') {x, y}, for if this is
the case, (ii) results. Likewise for y. Furthermore, if there are three distinct h
values as h ranges over either side of the partition, case (ii) results. The only
possibility is that there are two or fewer h values on either side of the partition.
Suppose there is only one h value = h0 on Vj,4. There are fewer than three h
values on V\b If there are two distinct h values on V\b, neither can match the
h value on V\a Every vertex in partite set A has the same neighborhood, so
that every vertex in partite set B is a source (if its h value is hi), or a sink (if
its h value is h2). Given that h0 ^ /q and h0 7^ h2, case (ii) results. Given that
h0 = hi, it is clear that if we cut x and y where h(x) = h0 and h(y) = h2l then
because n > 3 there are at least two vertices in part ite set A with the same value
[h + defc'p^j/}] = ho + defo, but that [h + defG/_{x ?/}] of an hi vertex, = hi +defi.
cannot have [hi + defi] = [ho + def0] unless all the vertices in set A and all the
hi vertices in set B are without loss of generality sources in G' {.r, ?/}. This
contradicts the fact that the vertices in partite sets A and B are incident.
If there are two h values on V\a, the only remaining possibility is that there
be two h values on V\b Then we have hi a fhA vertices and neighborhoods and
h\B< h2B vertices and neighborhoods. We necessarily have h^4 = for = 1,2.
Furthermore, without loss of generality [h + def] (v2a ) + 1 = [h + def](ri/i) 1,
and [h + defj(ui^) 1 = [h + def](u2s + 1). But then def(u2^) 2 = def(uis) and
def(ui^) 2 = def(r2/i). Therefore we have sets Ai,A2,Bi,B2 where Ai beats B2
72
beats A2 beats Bx beats Ax. The sizes of the sets are
\B2\ Bi 2 \A\  \A2\.
However, then 2\B2\ 2 = 21.411 and 2\BX\ + 2 = 2T2. Therefore, v4i =
T2 = \B2\ 1 = \B\ 1 + 1. But then there are 2 def values on and we get
hi+defo+2 and h2+def02 for values of [h+def] on V\A and hi+def0 and h2+def0
on V\B. If we assign an hi vertex from A then and an h2 vertex from B to x and
y, we get that we have a vertex from A with [h +d('fV;'{.r,,/}](r,2..i) = h2 + def0 and
a vertex from B with [h + defG/_{x y}](n1B) = hi + def0 2 when we cut x and y.
So then hx 2 h2. Then assign an h2 vertex from A and an hi vertex from B
to x and y. We get that we have a vertex from A with [h + ckT^;/_{.x,y}] ('l 1.4) =
hi + def0 + 4 and a vertex from B with [h + defG'{x,y}\{v2B) = h2 + def0 2
when we cut x and y. So then h2 2 = hi 2 2 = hj 4 = hi + 4. This final
contradiction completes the proof.
So there is one h value on l ,i and V\ b and one associated neighborhood
and case (i) results. To see that [h + def](x) = [h + defj(y) 2(n 1) also
results, notice that if def(x) = n, def(y) = n, (because team A beats team
B) and h is fixed on A and h is fixed on B. When we cut x and y. we get
def(rL4) + h{vXA) = def(n2B) + h(v2B) and so n 1 + h{vXA) = n + l + h(vXB)
and so h(vXA) h(viB) = 2(n 1).
Theorem 6.25 For all n > 3 and every feasible initial condition h : > Z
other than [h + def] (v) = c there is an (0, 0)avoiding irregular (0,1)labeling.
Proof: Let the bipartition of V(A'n>n) be AUB = V(/Ln,n) Suppose n < 4.
Consider digraph G' Kn^n with the initial condition h the zero function. Then
73
6.13 and 6.23 verify the theorem under these conditions, to get an irregular
labeling /*.
Let
h'(v) = h{v) + 1
h'fa) = h(v) 1
h'{v) = h(v) + 1
h'(v) = h{v) 1
if vx G A(A',)
if xv G A{Kn,n)
if vy G A(A'n,)
if yv G A{Kn
If [/;' + defG{x,y}\ is fixed over G" = G' {x. y}, then apply Theorem 6.15
and Lemma 6.16 in the case n = 3, apply induction in the case n = 4 and then
in both cases utilize /' = 1 / where /' is an irregular labeling of G" under h' to
complete the irregular (0, l)labeling of G'. (Here h! is feasible by Lemma 6.20.)
To see that in this case, f* = /' on G" and f* = 1 on G' G" is irregular and
(0. 0)avoiding, notice that [h + def] is distinct on V(G") under f* by definition
of h' and f' and that x and y have the greatest total weight and furthermore
[h + defj.r ^ [h + def] y under f*. Finally, /* is (0, 0)avoiding because the total
weight of both x and y is n. On the other hand, suppose [//' + dcfi;"] is not
fixed. Assign a G"'spanning double star of 0labels to arcs incident with X\ and
yi where x\ and y\ are as in Lemma 6.24, Case (ii). (The function h' remains
feasible on this restriction by Lemma 6.22.) Call this assignment of 0labels
/". Let G'" = G" {xi,yi} under h" = h!. The labeling can be completed by
74
producing (/"', G'". h") which exists by induction. Again form /* where
/*() = 1 if a e A{G' G")
/*() = 0 if a G A(G" G'")
/=/ if a G A(G'")
To see that /* is irregular and (0, 0) avoiding notice that /* produces g(x) ^
g(y) and that f* produces g(x i) ^ g(tj\) because [h + def]x ^ [h + def]y and
h'(x\) 7^ h'{y\). Finally observe that f* is distinct on G'" and that the total
weights of the vertices in G'" are properly between n (the weight of x) and 1
(the weight of x\). Since the weight of x\ and tj\ are both greater than zero it
is clear the labeling is (0, 0)avoiding.
If x and y do not exist as in case (ii), then the digraph G" is in Case
(i) of Lemma 6.24. Queue the vertices of G" and each partite set X\ =
Via, v2A, V(ni)A! Vi = Vib, V2B< , v(ni)B respectively. Label the arc between
ViA and VjB with a 1 if i + j > n 1 and a zero otherwise. It follows that
[h + def]^^) [/? + def(ujB)] = 2i 2(n 2) < 0 for all tiers of the construc
tion. Furthermore, different tiers have different total weight. In this case, f*
induces g(v) which is injective over V(G"), also, the total weight of x and y is n
which assures the labeling is (0. 0)avoiding and additionally demonstrates that
because this is greater than the total weight of any of the vertices in G" and
because [h + defj:r ^ [h + defjy we have the (0, l)labeling /* is irregular. Now
we consider the cases when n > 5.
75
Case 1: Now suppose n > 5, n odd. In this case, we can assign a G'spanning
double star of 1labels centered at {.r, y} that have [h + def](x) 7^ [h + def] ('
Subcase 1.1: If the set V(G') \
/' = 1 / of G" = G" {x, y) under ,
h'{v) = h{v) + 1
h'(v) = h(v) 1
h'(v) = h(v) + 1
h\v) = h(v) 1
x. y} fixes [h + def] use the labeling of
1' where
if vx e A(Kn^n)
if xv e A(Kn
if vy e A(Kn,n)
if yv G i4(A'n>n)
where / is available by induction. (The function h' is either feasible or the
labeling can be completed immediately by Lemma 6.20.) Define
f*(a) = 1 if a e A{G' G")
f*(a) = f(a) if a G A(G" G"').
To see that, /* is irregular notice, [h + def](x) 7 [h def] (?/) and that /* is
irregular on G" by definition of h' and /'. Furthermore, / is (0, 0)avoiding and
so the total weight of x and y is n which is greater than any of the vertices in
G" and large enough to show that f* is (0, 0)avoiding.
Subcase 1.2: If the function [h' + defr;"] is not fixed use Lemma 6.24 to
obtain a pair of vertices x\ and y\ both G V(G") which when labeled in a
G"spanning double star of 0labels, leaves [/?,' I clcfVv^{,r,.?/,}] nonfixed over
G'" = G" {xi,yi} and h'{x) 7^ h'(y). (The function h! remains feasible by
Lemma 6.22.) Use the inductive hypothesis to compute a labeling /"' on G"'
76
under h" = h! Define /
f*{a) = 1 if aeA(G'G")
f*(a) = 0 if a e A(G" G"')
f*(a) = f"'(a) if a G A(G"').
Case 2: Now suppose n > 6 is even. This case is identical to Case 1.
Definition 6.26 A n (n)avoiding irregular 2labeling of a digraph D is an ir
regular 2labeling such that no vertex has total weighted degree n under the
irregular 2labeling. An (2n)avoiding irregular 2labeling of a digraph D is an
irregular 2labeling such that no vertex has total weighted degree = 2n under the
irregular 2labeling.
Definition 6.27 Let an orientation of KnjL, called D be given. A function
h : V(D) > Z is called a feasible initial condition in the (n)avoiding case
unless unless D is oriented so that team A beats team B, H\a = d, h\s = c and
c d G (2n,4n 2), and in the (2n)avoiding case unless D is oriented so that
team A beats team B, Ii\a d, h\s = c and c d Â£ (2n + 2, 4n).
Lemma 6.28 Suppose h : V{D) > Z is feasible where D is an orientation of
77
I\nji (unth n <3). Then define h'
ti{v) = h(v) + 1
h'(v) = h(v) 1
h'(v) = h(v) + 1
h'(v) = h(v) 1
if vx Â£ A(Kn,n)
if xv Â£ A(KnM)
if vy Â£ A(Kn,n)
if yv Â£ A(Kntn).
where x andy are such that [ft. + def](x) 7^ [ft. + def](y). Then if ft/ is not feasible
on D {x,y} it follows that for some other choice of x and y, ft' is feasible on
D{x,y}.
Proof: Let A U B be the bipartition of V(D). Without loss of generality,
pick an element 2 of B such that it is not the only endpoint of a feedback arc
incident x. (The situation could be reversed selecting a vertex that is not the
only endpoint of a feedback arc incident y.) Pick an element w x from A.
Then ft' is feasible on D {w, z). For either ft'(x) 7^ ft'l^ or x is incident with
a feedback arc.
Lemma 6.29 Suppose ft : V(D) > Z is feasible where D is an orientation of
Kn n. Then define ft' by
ft'(u) = h(v) + 1 if vx Â£ A(Kn
ft'(u) = hfv) 1 if xv Â£ A{Knn)
h'(v) = h(v) + 1 if vy Â£ A(Kn:n)
hfv) = h(v)  1 if yv Â£ A(Kn,n).
where x andy are such that [ft + defj(x) ^ [ft h def] (2/). Then if IT is not feasible
on D {x,y} it follows that D has an (n)avoiding irregular 2labeling.
78
Proof: The proof for Lemma 6.20 applies.
Theorem 6.30 For n = 3, every orientation of Kn,n has an (n)avoiding and
a (2n)avoiding irregular 2labeling.
Proof: Consider the feedback graphs of size 1.2,3.4. There are two graphs
of size 2; there are four graphs of size 3; and three graphs of size 4. (In some
cases 2 placements of the feedback graphs must be considered.) In each case,
the vertices of the orientation can be permuted so that \i i + j > k then the arc
between and vjb is labeled with a 2 and otherwise the arc is labeled with a
1 is an irregular labeling. The value of k is 3 in the (n)avoiding case and 4 in
the (2n)avoiding case. See Appendix A for the completed proof.
Theorem 6.31 Every orientation 0/C4 with every feasible initial condition has
an (n)avoiding and a (2n)avoiding irregular 2labeling except in the two cases
forbidden by Theorem 6.15.
Proof: The proof is by cases. Appendix A.
Lemma 6.32 Let h : V{K^^) be a feasible initial condition on an orientation
ofK3,3, called G'. If the leave of a double star {xvib, ^hB^y, yv\A, yv2A} where
[def + h](x) [def + h](y), is one of the exceptional graphs (i.) or (ii.) from
Theorem 6.15, then without loss of generality [def + h](:r) 7^ [def + h](viB), and
the leave of {xv\b, XV2B, xV,vibvia, v\bV2a} is not (i.) or (ii.) under the
initial condition h' with h! defined by
79
h(v) = h(v) + 1
h'(v) = h(v) 1
ti(v) = h{ v) + 1
h'(v) = h(v) 1
if vx e A(Knn)
if e A(Knjl)
if vy e A(Kn
if yv e A(Kn n).
Proof:
Case 1: If we have an exceptional graph (i.) or (ii.) under forbidden con
ditions, and we select vm. and get the same exceptional graph under forbidden
conditions, then selecting v2b necessarily gives the other exceptional graph un
der nonforbidden feasible initial conditions except when we are in Case 2. We
get
[ti, ti, ti, ti] , [ti, ti. ti. ti] ^ [h'0, h'0 + 4,ti0 + 6, h'0 + 2],
or
[h'0, h'0 + 4, h'0 + 6, h'Q + 2] > [ti0, h*, h'0 + 6, ti0 + 2] ^ [ti, ti, ti, ti].
If permuting v\b and y does not return the same exceptional graph under
forbidden conditions, it returns a graph other than the ones underlying (i.), or
(ii.), or the same exceptional graph under allowable conditions, or the other
graph from the set under allowable conditions:
[ti0, /jq + 4, ti0 6,ti0 + 2] > [tiQ, ti, ti0 + 6, h0 + 2] ^ [h h h h ]
[ti, ti, ti, ti] [ti, ti, ti, ti] [ti0, ti0 + 4. h'0 + 6, ti0 + 2].
80
Case 2: In the exceptional case that [def + h](x) = [def + h](vis) or =
[def + h](v2B) and (ii.) is the leave, then we swap va or v2a for whichever
vertex does not have the same [/t + def] value as y; they are not the same. Under
this permutation, there is either
[/tg, /tg + 4, Hq + 6, /tg + 2] > [h.Q ) 4, /tg + 4, /tg + 6. /tg + 2] 7^ [/?/, h', h1, hf],
or
[hg, hg + 4, Hq + 6, h'0 + 2] > \h'0, /tg + 4, h0 + 6, /tg + 2] 7^ [//, /?/, h', h'],
or
[/tg. h'0 + 4, Ii'q + 6, /tg + 2] > [/tg + 2, h0 + 4, /tg + 6, h'0 + 2] 7^ [/? h h /;/],
or
[/tg, /tg + 4, /tg + 6, /tg + 2] > [/tg, /tg + 4. /tg + 6, /tg + 2] ^ [/i ,/i ,/i ,/?.],
and of course the charge matrices under permutation do not match [h'Q, h'0 +
4, /tg + 6, /tg + 2].
In the case that h'(x) = h'(v1B) h'(v2B), and (i.) is the leave, then we
swap v\a or ^2.4 for x. Since [def + h'](viA) = [def + h'](viB) 7^ [def + h'](y) this
permutation gives a leave which does not have one of the forbidden orientation
initial feasible condition combinations. If the orientation changes to (i.), the
fact that
[/?*, ti, ti, ti] ^ [ti0, /t'o + 4, /t'g + 6. h'0 + 2]
completes the proof.
81
Theorem 6.33 For n = 3 every feasible initial condition h : Kn.n Z gives
rise to a (2n) and (n)avoiding irregular 2labeling.
Proof: Let an orientation of A3.3, called G' = A'3,3, be given.
Suppose [h + def] is fixed by the vertex set of G'. Obtain a (0, 0)avoiding
(0,1) labeling / from Theorem 6.25 and let f = 1 + /; then f is a (2r?)avoiding
irregular 2labeling of G'. Suppose the labeling were not irregular. Then there
exists x and y in G' such that under h' we have g/(x) = g/{y), contrary to
construction.
Let x and y be such that [// + def] (3;) ^ [h + def](t/). Label a G'spanning
double star centered at x and y with 1labels. Then G' {x, y} is an orientation
of C4. For the restriction of h' to V(G' {x, y}). define
h'(v) = h(v) + 1 if vx G A{Kn,n)
h'(v) = h(v)  1 if xv G A{Kn
h'(v) = h(v) + 1 if liy G A(K1hn)
h'(v) = h(v)  1 if yv G A(Kn
(The function h! is feasible by Lemmas 6.28 and 6.29.) Notice, Lemma 6.32
allows that x and y can be selected so that Theorem 6.31 applies, and there
exists an (??.)avoiding irregular 2labeling of the oriented C'4. call it f. Define
f = f on G' {x, y} and / = 1 on G' (G1 {x. y}). Then / is a (2n)avoiding
irregular 2labeling of G'. To see this, notice there are vertices in both partite
sets incident with only 1labels: x and y. Consequently, the vertices x and y are
the only two vertices of total weight = 3, and they have g/(x) 7^ g/{'!]) Finally,
82
the vertices in G' {x. y} have gj distinct by the definition of /?' and /.
In the (n)avoiding case, suppose [h + 2def] is fixed by the vertex set of 6".
Obtain a (0, 0)avoiding (0,1) labeling / from Theorem 6.25, and let /' = 2 /;
then f' is an (n)avoiding irregular 2labeling of G'. Suppose the labeling were
not irregular. Then g/(x) = g/(y), under h' = 0, contrary to construction.
On the other hand, let x and y be such that [h + 2def](.z) [h + 2def](r/).
Label a G'spanning double star centered at x and y with 2labels. Then G'
{x, y} is an orientation of C4. For the restriction of h' to V{G' {x, y}), define
h' which is feasible by Lemma 6.29:
h'(v) = h(v) + 1
h'(v) = h(v) 1
h'(v) = h(v) + 1
h'(v) = h(v) 1
if vx e A{I\n,n)
if xv Â£ A(Kn,n)
if vy 6 A(Knttl)
if yv Â£ A{Kn,n).
Notice, Lemma 6.32 allows that x and y can be selected so that Theorem
6.31 applies and there exists an (2n)avoiding irregular 2labeling of the oriented
C4. call it /'. Define f = f on G' {z. y} and = 2 on G' (G! {x. y}). Then /
is an (n)avoiding irregular 2labeling of G'. To see this, notice there are vertices
in both partite sets incident with only 2labels: x and y. The vertices x and
y are the only two vertices of total weight = 6 and they have
Finally, the vertices in G' y} have gf distinct by the definition of h' and /.
Theorem 6.34 Every diregular orientation of /F4 4
has an (n)avoiding and a
83
(2n)avoiding irregular 2labeling. Moreover, the (n)avoiding labelings can be
formed from the (2n)avoiding labelings and vice versa because the digraph is
regular.
Proof: The proof is by two part construction. There are two cases to
consider, one where the feedback graph is a Hamiltonian cycle and one where
the feedback graph is a spanning pair of disjoint C4s. To see that the theorem
holds, notice the two figures Figure 6.1 and 6.2 show that there is an (n)avoiding
irregular 2labeling in each case. In each case, let / be the function which
describes the 2labeling. Let f'(a) = 3 f(a) for all arcs a in the digraph D,
and obtain a 2labeling in each case which is (2n)avoiding. It is easy to observe
that the labeling is irregular and the fact that the labeling is (2??)avoiding in
each case follows from the fact that there is no vertex of total weight (n) under
/'; if gp(v) = (n.n) then the arcs incident v are labeled with 2 under /' which
by definition of /' implies all the arcs incident with v are labeled with a 1 under
/. So then / is not (rc)avoiding contrary to construction.
Theorem 6.35 Every orientation of A"14 has an (n)avoiding irregular 2
labeling.
Proof: Let an orientation of A'4j4 called G' be given. The orientation is not
regular so that there exists a pair of vertices x and y such that 2def(x) 2def(y).
Label a G'spanning double star centered at x and y with 2labels. Let h' be
defined by h'(v) = h + 2 if v dominates x or y and h'(v) = h 2 if v is dominated
by x or y. If [/i + defj on is fixed by V(G' {x, y}) then obtain the (n)avoiding 2
labeling / which irregularly labels of G' {x, y} under h'. Let f = 3 / and label
84
G' {x, y} by /'. Let f* be defined by f*(a) = 2 for a G A(G' (G' {x, y}))
and f*(a) = /'(o) otherwise. Then f* is an (n)avoiding irregular 2labeling of
G'. We have gp(x) ^ gjiy). By definition h' and by definition /' it follows that
(jf* is distinct on V(G' {x, y}). The total weight of x and y is equals 8 and the
total weight of any other vertex is less than 8 since / was (n)avoiding and we
considered /' = 3 / (which is thus necessarily (2n)avoiding). So the function
f* is (n)avoiding, irregular, and uses two labels. If [h + defj is not fixed by the
vertices in G' {x, y) it follows that by Theorem 6.33 there exists /. an irregular
(2n)avoiding labeling that uses two labels under h!. So let /' = 3 / and let
f*(a) = 2 for a G A(G' (G' {.x, ?/})) and f*(a) = f'(a) if a G A(G' {x, y}).
This labeling /* is (n)avoiding irregular and uses two labels. In each case h'
is and remains feasible by Lemma 6.28 and 6.29 or else we can complete the
labeling in any case by Lemma 6.30 and 6.29.
Theorem 6.36 Every orientation of AT,4 has a (2n)avoiding irregular 2
labeling.
Proof: Assign a double star xv,xvc),xvQ,xy,yvi,yv2,yv?, and such that
def(x) 7^ def(y) and label all its arcs with 1. If the resulting A'3,3 is such that
2def(u) is fixed, use the labeling f = 3 / where / is given by Theorem 6.30
and is (2n)avoiding to complete the arc labeling; the completed arc labeling is
(2n)avoiding and uses two labels; to see that it is irregular check the weighted
degree pairs on V(A'3,3) For two degree pairs to match, we would have to have
gj{v) = gf(w) under the original labeling and this is contrary to the fact that
/ is irregular on A'3,3. In the remaining case, use Theorem 6.33 directly, this
85
time using an / given by the theorem which is (r?)avoiding. (Here we have a
feasible initial condition induced by the arcs of x and y.) Similar to the previous
theorem, we define h' in the standard wav and notice it is and remains feasible
by previous lemmas.
Theorem 6.37 For all n > 3 and every feasible initial condition h : KnM > Z
where [h + def] is not fixed there is an (n)avoidable irregular 2labeling. If
[h. + 2def] is not fixed, there is a (2n)avoidable irregular 2labeling.
*
Proof: Let a digraph G' = Kn n with the initial condition h = 0 and n < 4
be given. Then by Theorems 6.30, 6.35, and 6.36 the theorem is verified. Now
consider the case where h is not trivial. For n = 3, Theorem 6.33. establishes the
result. For n = 4, in the (2n)avoiding case, pick x and y such that [fi+def] is not
identical on x and y and label a double star of 1labels that spans the digraph
and is centered at these two vertices. Then if the remaining digraph, G' {a;, y}.
has [h + 2def] nonfixed, apply Theorem 6.33 in the (n)avoiding case. (Augment
h to h' as before.) The labeling obtained by pasting together the labeling from
Theorem 6.33 and the labeling on the rest of the digraph is irregular: the vertices
v V(A3,3) all have g(v) distinct and x and y have the smallest total weight
of any vertices in the digraph less than the total weight of the vertices in the
A^. If the remaining digraph has [h + 2def] fixed, apply Theorem 6.33 to obtain
/, an (2n)avoiding irregular 2labeling and use /' = 3 / to label the arcs of
the A3 3. Again, the vertices of A3 3 all have g(v) distinct and x and y have the
lowest possible total weight less than the weight of any of the other vertices.
By choice of x and r/, g(x) ^ g(y) Let n > 5 be odd. Then there exists a
86
pair of vertices x and y such that labeling a double star incident with these
two vertices x and y alternatively with 1 labels or 2 labels leaves [h + del] or
[h + 2def] of x and y distinct. In the case that [h + 2def] or [h + def] is not fixed
(on V' {x.y}); induction on the remaining vertices V {.r. y} gives (n) and
(2n)avoiding irregular 2 labelings and completes the proof. In the case that
[h + 2def] is fixed use 3 / where / is given by induction and (n)avoiding, or
in the case where [h + def] is fixed use 3 / where / is given by induction and
(2n)avoiding.
In the case where n > 6 and even, Kn.n is not regular, so pick x and y such
that either [h + def] or [h + 2def] are distinct depending on whether we want an
(n) or a (2n)avoiding irregular labeling and label a double star with 1 labels
or 2 labels. Then in the case that [h h def] or [h + 2def] is fixed on the remaining
vertices use 3 / where / is given in either the (2n) or (n)avoiding case. In
the case that these values are not fixed use induction.
This last theorem, taken together with Theorem 6.17 shows that s(Kn,n) = 2
where Kn.n is any orientation of Knn and n > 1.
87
