semi-regular relations and digraphs参考.pdf

MATHEMATICS
SEMI-REGULAR RELATIONS AND DIGRAPHS
BY
S. A. CHOUDUM *) AND K. R. PARTHASARATHY
(Communicated by Prof. N. G. DE BRUIJN at the meeting of January 29, 1972)
1. INTRODUCTION
A binary relation on a set V is a subset E of V x V. If for all v E V,
(v, v) 4 E, E is said to be irreflexive. A &graph is a pair (V, E) where
V is a set (called the vertex set) and E is an irreflexive relation on V.
The elements of E are the directed edges (or simply edges) of the digraph.
In traditional graph theory terminology a binary relation on V is a
digraph which admits loops, loops being edges of the form (v, v) E V x V.
If u E V, the out-degree of u is ]{v E V: (u, v) E E}I and in-degree of u is
1{v E V: (v, u) E E}I. A digraph in which each vertex has the same out-
degree r is called an out-regular digraph with index of out-regularity r.
In-regular digraphs are similarly defined. If a digraph is either out-regular
or in-regular we call it semi-regular. A digraph which is both out- and
in-regular with index r, is a regular &graph.
An out-regular digraph with index 1 is called a functional &graph
because such a digraph on a vertex set V corresponds in an obvious way
to a unique function f which maps V into V. An in-regular digraph with
inde