THE UN I V E R S I TY 0 -F MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Technical Report CONNECTIVITY IN DIGRAPHS Dennis P. Geller with assistance from: National Science Foundation Grant No. GN-2544 Washington, D. C.. and Department of Health, Education, and Welfare National Institutes of Health Grant No... GM-12236-05 Bethesda, Maryland and Department of rhe Navy Office of Naval Rese.arch'. Contract No. N00014-67-A-0181-O0011 Washington, D. C. and U. S. Army Research Office (Durham) Grant No. DA-31-124-ARO-D-483 Durham, North Carolina administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR July 1969 Distribution of This Document is Unlimited

A1 \~ ~ eN

ABSTRACT In this paper we extend the theory of connectivity from graphs to digraphs by introducing connectivity measures similar to the wellknown point- and line-connectivities for graphs. We discuss some simple upper and lower bounds for these parameters, and present classes of digraphs with various prescribed connectivities. Finally, we examine the many equivalent formulations of 2-connectedness for graphs and discuss the hierarchies of connectedness that their digraphical analogs suggest.

1. Measures of connectivity for digraphs We assume that the reader is familiar with the basic concepts of the theories of graphs and digraphs. We will rely almost exclusively on the notation presented in [23 and [3]. We first recall from [3] the notion of categories of connectedness. Let CO be the set of all disconnected digraphs. A digraph is strictly weak if it is weak but not unilateral; the set of all strictly weak digraphs is C1. A digraph is strictly unilateral if it is unilateral but not strong; the set of all strictly unilateral digraphs is C1. Finally, C3 is the set of all strong digraphs. If D C Ci it may be possible to remove a set S containing either only points or only arcs such that the resulting digraph D-S is in a different category C.. The minimumcardinality of such a set S can then serve as a measure of the connectivity of D. The (i,j)-connectivity Kij(D), defined only for digraphs D C Ci, is the minimum cardinality of any point set S such that D-S C C.. The (i,j)-line connectivity Xij(D), similarly defined only for D c Ci, is the minimum cardinality of any set S of arcs such that D-S C C.. Note that X.. cannot be defined for i < j. There are no similar restrictions for the numbers Kij, although Harary, Norman, and Cartwright [3, p.231] do note that there is no digraph D such that K13(D) = 1. Of course for D CiC. the values of KiO(D) and Xi (D) are the same as those of K and X for the graph which underlies D. There are many situations, for example, communication net and commodity network applications, where it is important only to insure that after removing points or lines the resulting digraph is in a different category, usually one with a lower index. The connectivity of a strong digraph D is ~3(D) = min {K3j(D) }.

The connectivity of a unilateral digraph is K3(D) = min {Kij (D) i = 2 or 3, D E C. and j = 0 or 1}. The connectivity of a weak digraph is K1(D) = Kio(D), where D ~ Ci. The corresponding line-connectivities are. defined accordingly: X3(D) = min {X3j(D)} X2(D) = min {Xij(D)ji = 2 or 3, D c Ciand j = 0 or 1} X1(D) = X (D) where D c C.. Two final definitions will prove convenient. A tournament Tn has n points and exactly one arc between every two points; of course, there are many tournaments with n > 2 points. The complete symmetric digraph Kn has n points and an oriented pair of arcs between every two points.

3 2. Bounds on the connectivity of digraphs The indegree id(v), outdegree od(v), and total degree td(v) of a point v are familiar concepts: let 6id' 6od' and 6td be the respective minima of these functions over all the points of a digraph D, and set ((S a (2) = min (id od). Let be min {id(v) + 6id(D-v)l v C D}; define id iLet 6 bmid (2) (2) (aa2)y a(2)mo od similarly and then set 6(2) in (id) 6od )) (2) d (2) Note that each of () and (od can be realized by starting with a point v of minimum in- or outdegree. Theorem 1. For any digraph D for which the parameters are defined, a. K < <6 K1 < 1 < 6td b. K2 < 2 6( c. K3 K 3 <6 Proof. The first result is due to Whitney [4]. For (c), let v be a point in D with od(v) = 6od and remove the outbundle of v from D to get D'. Then if u c D there will be no v - u path in D', which therefore cannot be strong; thus <' 6od and so by duality, 5 < 6. Now, note that if D has X = 1 then X K3 = 1. Otherwise, choose X3 - 1 arcs of D whose removal leaves a digraph D' with 3,2 = 1, and let uv be an arc such that D' - uv C C2. Remove one endpoint of each of the other;3 - 1 arcs from D, leaving both u and v if possible. The resulting digraph, if still strong, has 3 2 = 1, and hence K3 < 3. The proof for part (b) is similar. We begin by choosing u and v such that id(u) = 6id and idD_u(v) = did6 (D-u) Remove the inbundles of both u and v from D and the points will be weakly separated in the resulting digraph. Application of duality then yields X2 < 6 K <_ X follows as above.

4 Having demonstrated these inequalities it is natural to ask how independent the three parameters are. Chartrand and Harary [1] answered that question for graphs by constructing graphs with all possible values of K < X < 6. We do the same for each of the inequalities of Theorem 1. Samples of these constructions are given in Figures 1-3. Construction 1. To construct digraphs with K1 = k, X1 = 6id = d take id two tournaments Td+l and T'd+l with point sets {u1,...,ud+l} and {v1,...,vd+l} respectively. To the digraph Td+l U T'd+l add arcs from points u1,...,uk to points Vl,...,v, as evenly distributed among the u. as possible. Then unless K = d we have 6td = d, = and K = k. td ~ 3; d Z ad'1 1 If K = d we instead take Td+l and add a new point w with arcs {wuiJ i = 1,...,d}. Note that either of these graphs can be made strong or unilateral by appropriate re-orientation. Construction 2. We are given K2 = k 2 = < 6(2) = d = min (6) 6 ); 2 d 2e nid od without loss of generality take j = 6od 6id < d. We need concern ourselves with six different sets of points: two copies of K2d, one copy of Kd, and two points wl and w2. There will be an arc between wl (1and each point of K): d-j of the arcs will be directed from wl There and each point of K2d will be arcs from Kk to K2d), distributed as evenly as possible among the points of Kk We then add all arcs from K2d) to Kk again distributed 2d' (2) as evenly as possible. There is an arc between w2 and each point of K2d, k of these directed away from w2. There are all arcs from Kd to each of w1 and w2, and all arcs in both directions between Kd and Kk. Construction 3. Begin with two copies of Kd, d =6, and k = K additional points wi. Add all arcs from Kd) to the w. and from the wi to Kd 2) and Q = Xg arcs from K) to distributed as evenly as possible among the points.

K1 = i, 2, 6 = 3 Figure 1.

6 K2 = 1, X2 = 2, (2) = 3 Figure 2.

K3 = 1, X3 = 2, 6 = 3 Figure 3.

8 We now proceed to develop some additional bounds on the connectivity K' Recall that the condensation D of a digraph D has for points the strong components Si of D, with SiSj. D if and only if there are points u S.iv e Sj such that uv e D. Theorem 2. For any strong digraph D with p points, if 6 > ptn-2 then K3 < n. Proof. Suppose that 6 > p+n-2 but there is a set S with ISI = n - 1 2 such that D-S is not strong. Let D1, D2,..., Dt be the strong components of D-S and without loss of generality choose Dlsuch that {D1I > (p-n+l)/2. Now, any point v e D1 can be adjacent both to and from all the points of S. However, if Di is any other strong component of D-S then all lines between D1 and Di are either all into Di or all out of D.. So, since the condensation (D-S) has at least one transmitter and one receiver, we also p-n-l p+n-3 choose D1 so that v E D1 implies that in D, 6(v)< + n-l = a contradiction. Theorem 3. If D is a strong digraph with p points and q arcs, then K3<[q/p]. Proof. If [q/p] = r then if D has a point v1 with min (id(v1), od(vl)) > r there is also a point v2 with min (idv2, odv2) < r. Otherwise all points v have idv = odv = r and, in either case K 3<r by Theorem 1. To show that equality is possible for a given q and p, we begin with a directed cycle with p points having arcs {vivi+l }, and then add arc vivj whenever j-i - m (mod p) for 2 < m < [q/p]. (Of course if [q/p] = 1 then the directed cycle is itself the desired example.) The resulting digraph D has p[q/p] arcs; we claim that K3(D) = [q/p] so that by the first part of the theorem we can get an example by adding q - p[q/p] arcs arbitrarily.

Now suppose that [q/p] - 1 points have been removed from D. The remaining points lie on segments of the original cycle, so it is sufficient to show that there is a walk from the last point of one segment to the first point of the next. Suppose the last point of a segment is v and that n1 the first point of the next segment is Vn2 in2-nl[ > 1, and that (modulo p) n2-nlE{2,..., [i]}. Then at least [p ] points must have been removed from the cycle between vn and vn, a contradiction. n1~~~

10 3. Nonseparable digraphs Among the simplest and best known of theorems in graph tneory is the one which describes the many equivalent conditions for a graph to be a block. It would not seem to be unreasonable to expect many of these to carry over into an equivalent theorem for digraphs. Unfortunately this does not quite happen. In particular, as we shall see, what would seem to be the natural analog of the so-called "cyclic connectivity" theorem does not hold. Theorem 4. For any strong digraph D,K3 > 2 if and only if, given any three points, there is a path between any two which avoids the third. Proof. Necessity is obvious, since if there are points u,v,w such that each u-v path contains w then D-w is not strong. For sufficiency, note that there can be no point w such that D-w is not strong. Among the other equivalent conditions for a graph G to be a block are [2]: 1. Every two points lie on a common cycle. 2. Every point and arc lie on a common cycle. 3. Every two arcs lie on a common cycle. 4. For every three distinct points,there is a path joining any two which contains the third. 5. Given any two points and one arc there is a path joining the points which contains the arc. For digraphs we can get additional conditions by modifying 4. and 5. and the condition of the previous theorem. 4'. For any u, v, w there is either a u-v path or a v-u path which contains the third. S'. Given any points u, v and arc x there is a u-v path or a v-u path which contains x. 6. For any u, v, w there is either a u-v path or a v-u path which avoids w.

11 We proceed to demonstrate the various implications and non-implications among these statements. We first note that condition 6 is just the analog of Theorem 4 for the parameter K2. Corollary. For any unilateral digraph D K > 2 if and only if condition 6 holds. If every two arcs lie on a common cycle then D must be a cycle for, if D has a point u with id > 2 (or dually, od > 2), there are two arcs in D which cannot belong to any cycle. There are non-trivial examples of graphs for which every point and arc lie on a common cycle; the digraph D1 in Figure 4 is one such; note that the points labeled u2 are to be identified. This, however, has two points u such that D- u 1 i D:. Figure 4. is not strong. Conversely in the digraph D2 shown in Figure 5, K3 = 2 but u and x lie on no common cycle. u D2: Figure 5.

12 One of the more surprising of the graphical equivalences is that between Theorem 3 and Condition 4. For digraphs only one implication holds. Theorem 4. If for each triple u, v, w of distinct points there is a u-w path containing v then for each triple u, v, w of distinct points there is a u-w path avoiding v; i.e., K3 > 2. Proof. Consider points u, v, w. There is a u-v path P containing w. Then the subpath P[u,w] avoids v. A counterexample to the converse of this theorem is given by D3 in Figure 6: there is no u-v path containing w. v D3 w u Figure 6. The strong form of condition 5 is clearly not necessary for K3> 2; D2 is an example of this. On the other hand, it is certainly a sufficient condition. Theorem 5. If for every pair u,v of distinct points and any arc x there is a u-v path containing x, then K3 > 2.

13 Theorem 6. If for every pair, u,v of distinct points and any arc x there is either a u-v path containing x or a v-u path containing x, then D is strong or D has exactly 2 points and one arc. Proof. Suppose D has three points. Let p = u,v,w be a path of length 2. Then there must be a w-v path containing uv, and hence there is a w-u path. On the other hand, if arcs uv and wv form a semipath in D then there must be paths from u to v and from v to u. It follows immediately that any two points joined by a seimpath are mutually reachable, so that since D is obviously weak it must be strong. This weak form (5') of condition 5 is clearly not even necessary for a digraph to have K3 > 2; in fact, it is not necessary for K3 > 1. Conversely, the digraph D4 shown in Figure 7 is an example for which 5' holds but K3 1 D4 Figure 7. Corollary If 5' holds then K2 > 2. Condition 4' is also not necessary for a digraph to be strong, as the strong digraph D5 in Figure 8 has neither a u-v or a v-u path which contains w. u w 5. Figure 8.

14 Since any hamiltonian digraph, such as D4, satisfies 4', it is certainly not sufficient for a digraph to have K3 > 2. It is, however, sufficient for K3 > 1. We note in passing that 4' is not sufficient for a digraph to be hamiltonian, as D6 of Figure 9 shows: D6: Figure 9. Condition 6 is necessary for a digraph to have K3 > 2 since its stronger form is equivalent to K3 >2. It is certainly not sufficient since the digraph D7 in Figure 10 satisfies the condition but is not strong. D7 7Figure 10. Figure 10.

15 Condition 1 is the best known of the graphical equivalences, the analog of the cyclic connectivity theorem in topology. Since D6 has this property, as does any cycle, the equivalence fails for digraphs. In fact, it fails in both directions: it is not difficult to verify that while K3(D8) = 2, u and v lie on no directed cycle; similarly for Dg which is obviously the smallest such graph, and which was contributed by Ronald Brender. D8: v v Figure 11. Dg: Figure 12.

1-6 REFERENCES 1. G. Chartrand and F. Harary, Graphs with prescribed connectivities, Theory of Graphs, P. Erdos and G. Katona, editors, Academic Press, New York, 1968. 2. F. Harary, Graph Theory, Addison-Wesley, Cambridge, 1969. 3. F. Harary, R. Norman and D. Cartwright, Structural Models, John Wiley & Sons, New York, 1965. 4. H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, (1932) 150-168.

UNCLASSIFIED Security Classification DOCUMENT CONTROL DATA - R&D (Security claetlfication of title, body of abstract and indexing annotation must be entered when the overtll report is claseifled) 1. ORIGINATIN G ACTIVITY (Corporate author) 2a. REPORT SECURITY C LA$SSIFICATION LOGIC OF COMPUTERS GROUP Unclassified The University of Michigan 2b. GROUP Ann Arbor, Michigan 48104 3. REPORT TITLE CONNECTIVITY IN DIGRAPHS 4. DESCRIPTIVE NOTES (Typo of report and Inc.uslve datee) Technical Report S. AUTHOR(S) (Lest namne. first name, nitial) Geller, Dennis P. 6. REPO RT DATE 7a. TOTAL NO. OF PAGES 7b. NO. OF RErs July 1969 17 4 18a. CONTRACT OR GRANT NO. 9S. ORIGINATOR'8 REPORT NUMBER(S) DA-31-124-ARO-D-483 b. PROJECT NO. 08226-13-T c. sb. OT s b RT PORT NO(S) (Any other number that may be a.lsgned tis report) 10. A VAIL AILITY/LIMITARtON NOTICES Distribution of This Document is Unlimited. 1 1. SUPPL EMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY U. S. Army Research Office (Durham) Durham, North Carolina 13. ABSTRACT In this paper we extend the theory of connectivity from graphs to digraphs by introducing connecitivity measures similar to the well-known point- and line-connectivities for graphs. We discuss some simple upper and lower bounds for these parameters, and present classes of digraphs with various prescribed connectivities. Finally, we examine the many equivalent formulations of 2-connectedness for graphs and discuss the hierarchies of connectedness that their digraphical analogs suggest. DD |1F4?'64 1473 UNCLASSIFIED Security Classification

UNCLASSIFIED II IIII111111111111l1 Security Classification 3 9015 02826 0787 14. LINK A LINK 8 LINK C KEY WORDS ROLE WT I ROLE WT ROLE T graphs digraphs connectivity line-connectivity INSTRUCTIONS 1. ORIGINATING ACTIVITY: Enter the name and address imposed by security classification, using standard statements of the contractor, subcontractor, grantee, Department of De- such as: fense activity or other organization (corporate author) issuing (1) "Qualified requesters may obtain copies of this the report. report from DDC" 2a. REPORT SECURITY CLASSIFICATION: Enter the over(2) "Foreign announcement and dissemination of this all security classification of the report. Indicate whether "Restricted Data" is included. Marking is to be in accordance with appropriate security regulations. (3) "U. S. Government agencies may obtain copies of this report directly from DDC. Other qualified DDC 2b. GROUP: Automatic downgrading is specified in DoD Di- users shall request throm Dugh Other qualified DDC rective 5200.10 and Armed Forces Industrial Manual. Enter the group number. Also, when applicable, show that optional,, markings have been used for Group 3 and Group 4 as author- (4) "U. S. military agencies may obtain copies of this ized. report directly from DDC. Other qualified users 3. REPORT TITLE: Enter the complete report title in all shall request through capital letters. Titles in all cases should be unclassified. If a meaningful title cannot be selected without classification, show title classification in all capitals in parenthesis (5) "All distribution of this report is controlled Qualimmediately following the title. ified DDC users shall request through 4. DESCRIPTIVE NOTES: If appropriate, enter the type of. report, e.g., interim, progress, summary, annual, or final. If the report has been furnished to the Office of Technical Give the inclusive dates when a specific reporting period Is Services, Department of Commerce, for sale to the public, indicovered. cate this fact and enter the price, if known. 5. AUTHOR(S): Enter the name(s) of author(s) as shown on 11. SUPPLEMENTARY NOTES: Use for additional explanaor in the report. Enter last name, first name, middle initial. tory notes. If military, show rank and branch of service. The name of the principal author is an absolute minimum requirement. 12. SPONSORING MILITARY ACTIVITY: Enter the name of the departmental project office or laboratory sponsoring (pay6. REPORT DATE. Enter the date of the report as day, ing for) the research and development, Include address. month, year, or month, year. If more than one date appears on the report, use date of publication, 13. ABSTRACT: Enter an abstract giving a brief and factual summary of the document indicative of the report, even though 7a. TOTAL NUMBER OF PAGES: The total page count it may also appear elsewhere in the body of the technical reshould follow normal pagination procedures, i.e., enter the port. If additional space is required, a continuation sheet shall number of pages containing information. be attached. 7b. NUMBER OF REFERENCES: Enter the total number of It is highly desirable that the abstract of classified reports references cited in the report. be unclassified. Each paragraph of the abstract shall end with 8a. CONTRACT OR GRANT NUMBER: If appropriate, enter an indication of the military security classification of the inthe applicable number of the contract or grant under which formation in the-paragraph, represented as (TS). (S), (C) or (U). the report was written. There is no limitation on the length of the abstract. How8b, 8c, & 8d. PROJECT NUMBER: Enter the appropriate ever, the suggested length is from 150 to 225 words. military department identification, such as project number, 14. KEY WORDS: Key words are technically meaningful terms!bocnmryenmrtsnb.......... 14. KEY WlORDS: Key words are technically meaningful terms subproject number, system numbers, task number, etc,. subprojectnumber, system numberstasknumber, etor short phrases that characterize a report and may be used as 9a. ORIGINATOR'S REPORT NUMBER(S): Enter the offi- index entries for cataloging the report. Key words must be cial report number by which the document will be identified selected so that no security classification is required. Identiand controlled by the originating activity, This number must fiers, such as equipment model desigiation, trade name, military be unique to this report. project code name, geographic location, may be used as key 9b. OTHER REPORT NUMBER(S): If the report has been words but will be followed by an indication of technical conassigned any other report numbers (either by the originator text. The assignment of links, rules, and weights is optional. or by the aponsor), also enter this number(s). 10. AVAILABILITY/LIMITATION NOTICES: Enter any lir- itations on further dissemination of the report. other than those.UNCLASSIFIED Security Classification