4.3.4.4. four parameters/one final graph

Proposition 110 Let Ξ± denote max(0,𝐍𝐂𝐂-1).

ππ€π‘π‚β‰€Ξ±Β·πŒπ€π—_𝐍𝐂𝐂 2 +𝐌𝐈𝐍_𝐍𝐂𝐂 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΌπ‘…πΆπ‘ˆπΌπ‘‡:ππ€π‘π‚β‰€Ξ±Β·πŒπ€π—_𝐍𝐂𝐂+𝐌𝐈𝐍_𝐍𝐂𝐂

𝐚𝐫𝐜_𝐠𝐞𝐧=𝐢𝐻𝐴𝐼𝑁:𝐍𝐀𝐑𝐂≀α·(2Β·πŒπ€π—_𝐍𝐂𝐂-2)+2·𝐌𝐈𝐍_𝐍𝐂𝐂-2

𝐚𝐫𝐜_𝐠𝐞𝐧∈{πΆπΏπΌπ‘„π‘ˆπΈ(≀),πΆπΏπΌπ‘„π‘ˆπΈ(β‰₯)}:ππ€π‘π‚β‰€Ξ±Β·πŒπ€π—_𝐍𝐂𝐂·(πŒπ€π—_𝐍𝐂𝐂+1) 2+𝐌𝐈𝐍_𝐍𝐂𝐂·(𝐌𝐈𝐍_𝐍𝐂𝐂+1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧∈{πΆπΏπΌπ‘„π‘ˆπΈ(<),πΆπΏπΌπ‘„π‘ˆπΈ(>)}:ππ€π‘π‚β‰€Ξ±Β·πŒπ€π—_𝐍𝐂𝐂·(πŒπ€π—_𝐍𝐂𝐂-1) 2+𝐌𝐈𝐍_𝐍𝐂𝐂·(𝐌𝐈𝐍_𝐍𝐂𝐂-1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ):ππ€π‘π‚β‰€πŒπˆπ_𝐍𝐂𝐂 2 -𝐌𝐈𝐍_𝐍𝐂𝐂+Ξ±Β·(πŒπ€π—_𝐍𝐂𝐂 2 -πŒπ€π—_𝐍𝐂𝐂)

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπ‘ŒπΆπΏπΈ:𝐍𝐀𝐑𝐂≀2Β·Ξ±Β·πŒπ€π—_𝐍𝐂𝐂+2·𝐌𝐈𝐍_𝐍𝐂𝐂

𝐚𝐫𝐜_𝐠𝐞𝐧=𝑃𝐴𝑇𝐻:𝐍𝐀𝐑𝐂≀α·(πŒπ€π—_𝐍𝐂𝐂-1)+𝐌𝐈𝐍_𝐍𝐂𝐂-1

Proof 110 We construct 𝐍𝐂𝐂-1 connected components with πŒπ€π—_𝐍𝐂𝐂 vertices and one connected component with 𝐌𝐈𝐍_𝐍𝐂𝐂 vertices. n 2 corresponds to the maximum number of arcs in a connected component. n, 2Β·n-2, nΒ·(n+1) 2, nΒ·(n+1) 2, nΒ·(n-1) 2, nΒ·(n-1) 2, n 2 -n, 2Β·n and n-1 respectively correspond to the maximum number of arcs in a connected component of n vertices according to the fact that we use the arc generator πΆπΌπ‘…πΆπ‘ˆπΌπ‘‡, 𝐢𝐻𝐴𝐼𝑁, πΆπΏπΌπ‘„π‘ˆπΈ(≀) πΆπΏπΌπ‘„π‘ˆπΈ(β‰₯) πΆπΏπΌπ‘„π‘ˆπΈ(<) πΆπΏπΌπ‘„π‘ˆπΈ(>) πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ) πΆπ‘ŒπΆπΏπΈ or 𝑃𝐴𝑇𝐻.

Proposition 111

𝐍𝐂𝐂>0⇒𝐍𝐀𝐑𝐂β‰₯(𝐍𝐂𝐂-1)Β·max(1,𝐌𝐈𝐍_𝐍𝐂𝐂-1)+max(1,πŒπ€π—_𝐍𝐂𝐂-1)

𝐚𝐫𝐜_𝐠𝐞𝐧=𝑃𝐴𝑇𝐻:𝐍𝐀𝐑𝐂β‰₯max(0,𝐍𝐂𝐂-1)Β·(𝐌𝐈𝐍_𝐍𝐂𝐂-1)+πŒπ€π—_𝐍𝐂𝐂-1

Proof 111 (165) We construct 𝐍𝐂𝐂-1 connected components with 𝐌𝐈𝐍_𝐍𝐂𝐂 vertices and one connected component with πŒπ€π—_𝐍𝐂𝐂 vertices. The quantity max(1,n-1) corresponds to the minimum number of arcs in a connected component of n (n>0) vertices.

Proposition 112

𝐍𝐕𝐄𝐑𝐓𝐄𝐗≀max(0,𝐍𝐂𝐂-1)Β·πŒπ€π—_𝐍𝐂𝐂+𝐌𝐈𝐍_𝐍𝐂𝐂

Proposition 113

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯max(0,𝐍𝐂𝐂-1)·𝐌𝐈𝐍_𝐍𝐂𝐂+πŒπ€π—_𝐍𝐂𝐂

Proposition 114

ππ’πˆππŠ+ππ’πŽπ”π‘π‚π„β‰€ππ‚π‚Β·max(0,πŒπ€π—_𝐍𝐂𝐂-1)

Proof 114 Since a connected component contains at most πŒπ€π—_𝐍𝐂𝐂 vertices and since it does not contain any isolated vertex and since a same vertex cannot be both a sink and a source a connected component involves at most πŒπ€π—_𝐍𝐂𝐂-1 sinks and sources alltogether. Thus the result follows.

Proposition 115

𝐍𝐀𝐑𝐂≀max(0,𝐍𝐒𝐂𝐂-1)Β·πŒπ€π—_𝐍𝐒𝐂𝐂 2 +𝐌𝐈𝐍_𝐍𝐒𝐂𝐂 2 + max(0,𝐍𝐒𝐂𝐂-1)·𝐌𝐈𝐍_ππ’π‚π‚Β·πŒπ€π—_𝐍𝐒𝐂𝐂+ πŒπ€π—_𝐍𝐒𝐂𝐂 2 Β·max(0,𝐍𝐒𝐂𝐂-2)Β·max(0,𝐍𝐒𝐂𝐂-1) 2

Proof 115 We assume that we have at least two strongly connected components (the case with one being obvious). Let (SCC i ) i∈[𝐍𝐂𝐂(G)] be the family of strongly connected components of G. Then |E(G)|β‰€βˆ‘ i∈[𝐍𝐂𝐂(G)] |E(G[SCC i ])|+k, where k is the number of arcs between the distinct strongly connected components of G. For any strongly connected component SCC i the number of arcs it has with the other strongly connected components is bounded by |SCC i |Β·(|V(G)-SCC i |). Consequently, k≀1 2Β·βˆ‘ i∈[𝐍𝐂𝐂(G)] |SCC i |Β·(|V(G)-SCC i |). W.l.o.g. we assume |SCC 1 |=𝐌𝐈𝐍_𝐍𝐂𝐂. Then we get k≀1 2Β·(𝐌𝐈𝐍_𝐍𝐂𝐂·(𝐍𝐂𝐂-1)Β·πŒπ€π—_𝐍𝐂𝐂+πŒπ€π—_𝐍𝐂𝐂·((𝐍𝐂𝐂-2)Β·πŒπ€π—_𝐍𝐂𝐂+𝐌𝐈𝐍_𝐍𝐂𝐂)).

Proposition 116

𝐍𝐀𝐑𝐂β‰₯max(0,𝐍𝐒𝐂𝐂-1)·𝐌𝐈𝐍_𝐍𝐒𝐂𝐂+πŒπ€π—_𝐍𝐒𝐂𝐂

Proof 116 Let (SCC i ) i∈[𝐍𝐂𝐂(G)] be the family of strongly connected components of G, as |E(G)|β‰₯βˆ‘ i∈[𝐍𝐂𝐂(G)] |E(G[SCC i ])|, we obtain the result since in a strongly connected graph the number of edges is at least its number of vertices.

Proposition 117

𝐍𝐕𝐄𝐑𝐓𝐄𝐗≀max(0,𝐍𝐒𝐂𝐂-1)Β·πŒπ€π—_𝐍𝐒𝐂𝐂+𝐌𝐈𝐍_𝐍𝐒𝐂𝐂

Proposition 118

𝐍𝐕𝐄𝐑𝐓𝐄𝐗β‰₯max(0,𝐍𝐒𝐂𝐂-1)·𝐌𝐈𝐍_𝐍𝐒𝐂𝐂+πŒπ€π—_𝐍𝐒𝐂𝐂

Proposition 119 Let Ξ±, Ξ² and Ξ³ respectively denote max(0,𝐍𝐂𝐂-1), 𝐍𝐕𝐄𝐑𝐓𝐄𝐗-α·𝐌𝐈𝐍_𝐍𝐂𝐂 and 𝐌𝐈𝐍_𝐍𝐂𝐂.

𝐍𝐀𝐑𝐂≀α·γ 2 +Ξ² 2

𝐚𝐫𝐜_𝐠𝐞𝐧∈{πΆπΏπΌπ‘„π‘ˆπΈ(≀),πΆπΏπΌπ‘„π‘ˆπΈ(β‰₯)}:𝐍𝐀𝐑𝐂≀α·γ·(Ξ³+1) 2+Ξ²Β·(Ξ²+1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧∈{πΆπΏπΌπ‘„π‘ˆπΈ(<),πΆπΏπΌπ‘„π‘ˆπΈ(>)}:𝐍𝐀𝐑𝐂≀α·γ·(Ξ³-1) 2+Ξ²Β·(Ξ²-1) 2

𝐚𝐫𝐜_𝐠𝐞𝐧=πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ):𝐍𝐀𝐑𝐂≀α·γ·(Ξ³-1)+Ξ²Β·(Ξ²-1)

Figure 4.3.7. Illustration of PropositionΒ 119(174). Graphs that achieve the maximum number of arcs according to a minimum number of vertices in a connected component, to a number of connected components, as well as to a fixed number of vertices (𝐌𝐈𝐍_𝐍𝐂𝐂=2,𝐍𝐂𝐂=5,𝐍𝐕𝐄𝐑𝐓𝐄𝐗=11,𝐍𝐀𝐑𝐂=(11-(5-1)Β·2) 2 +(5-1)Β·2 2 =25)
ctrs/narc_leq_minncc_ncc_nvertex

Proof 119 For proving inequalityΒ 174 we proceed by induction on the number of vertices of G. First note that if all the connected components are reduced to one element the result is obvious. Thus we assume that the number of vertices in the maximal sized connected component of G is at least 2. Let x be an element of the maximal sized connected component of G. Then, G-x satisfies Ξ±(G-x)=Ξ±(G), Ξ³(G-x)=Ξ³(G) and Ξ²(G-x)=Ξ²(G)-1. Since by induction hypothesis |E(G-x)|≀α(G-x)Β·Ξ³(G-x) 2 +Ξ²(G-x) 2 , and since the number of arcs of G incident to x is at most 2Β·(Ξ²(G)-1)+1, we have that |E(G)|≀α(G)Β·Ξ³(G) 2 +(Ξ²(G)-1) 2 +2Β·(Ξ²(G)-1)+1. And thus the result follows.

Proposition 120

𝐍𝐀𝐑𝐂≀𝐍𝐂𝐂-1+(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐒𝐂𝐂+1)Β·(𝐍𝐕𝐄𝐑𝐓𝐄𝐗-𝐍𝐂𝐂+1)+(𝐍𝐒𝐂𝐂-𝐍𝐂𝐂+1)Β·(𝐍𝐒𝐂𝐂-𝐍𝐂𝐂) 2

Figure 4.3.8. Illustration of PropositionΒ 120. A graph that achieves the maximum number of arcs according to a fixed number of connected components, to a fixed number of strongly connected components as well as to a fixed number of vertices (𝐍𝐂𝐂=3,𝐍𝐒𝐂𝐂=6,𝐍𝐕𝐄𝐑𝐓𝐄𝐗=7,𝐍𝐀𝐑𝐂=3-1+(7-6+1)Β·(7-3+1)+(6-3+1)Β·(6-3) 2=18)
ctrs/narc_leq_ncc_nscc_nvertex

Proof 120 We proceed by induction on T(G)=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-|X|-(𝐍𝐂𝐂(G)-1), where X is any connected component of G of maximum cardinality. For T(G)=0 then either 𝐍𝐂𝐂(G)=1 and thus the formula is clearly true, by PropositionΒ 145 or all the connected components of G, but possibly X, are reduced to one element. Since isolated vertices are not allowed, again by PropositionΒ 145 applied on G[X], the formula holds indeed 𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G[X])=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-(𝐍𝐂𝐂(G)-1) and 𝐍𝐒𝐂𝐂(G[X])=𝐍𝐒𝐂𝐂(G)-(𝐍𝐂𝐂(G)-1).

Assume that T(G)β‰₯1. Then there exists Y, a connected component of G distinct from X, with more than one vertex.

  • Firstly assume that G[Y] is strongly connected. Let y∈Y and let G ' be the graph such that V(G ' )=V(G) and E(G ' ) is defined by:

    • For all Z connected components of G distinct from X and Y we have G ' [Z]=G[Z].

    • With X ' =Xβˆͺ(Y-{y}) and Y ' ={y}, we have E(G ' [Y ' ])={(y,y)}, E(G ' [X ' ])=E(G[X])βˆͺ{(z,x):z∈Y-{y},x∈X}βˆͺ{(z,t):z,t∈Y-{y}}.

    Clearly we have that |E(G ' )|-|E(G)|β‰₯(|Y|-1)Β·|X|-2Β·(|Y|-1) and since |X|β‰₯|Y|β‰₯2, the difference is positive or null. Now as 𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G ' )=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G), 𝐍𝐂𝐂(G ' )=𝐍𝐂𝐂(G), 𝐍𝐒𝐂𝐂(G ' )=𝐍𝐒𝐂𝐂(G) (since G ' [Y-{y}] is strongly connected because E(G ' [Y-{y}])={(z,t):z,t∈Y-{y}} and since the reduced graph of the strongly connected components of G ' [X ' ] is exactly the reduced graph of the strongly connected components of G[X] to which a unique source has been added) and as T(G ' )≀T(G)-1, the result holds by induction hypothesis.

  • Secondly assume that G[Y] is not strongly connected. Let ZβŠ‚Y such that Z is a strongly connected component of G[Y] corresponding to a source in the reduced graph of the strongly connected components of G[Y]. Let G ' be the graph such that V(G ' )=V(G) and E(G ' ) is defined by:

    • For all W connected components of G distinct from X and Y we have G ' [W]=G[W].

    • With X ' =XβˆͺZ and Y ' =Y-Z, we have E(G ' [Y ' ])=E(G[Y ' ]) if |Y ' |>1 and E(G ' [Y ' ])={(y,y)} if Y ' ={y}. E(G ' [X ' ])=E(G[X])βˆͺ{(z,x):z∈Z,x∈X}.

    Clearly we have that |E(G ' )|-|E(G)|β‰₯|Z|Β·|X|-|Z|Β·(|Y|-|Z|) and since |X|>|Y|-|Z|, the difference is strictly positive. Now as 𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G ' )=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G), 𝐍𝐂𝐂(G ' )=𝐍𝐂𝐂(G), 𝐍𝐒𝐂𝐂(G ' )=𝐍𝐒𝐂𝐂(G) and as T(G ' )≀T(G)-1, the result holds by induction hypothesis.

Proposition 121

𝐍𝐀𝐑𝐂β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗-max(0,min(𝐍𝐂𝐂,𝐍𝐒𝐂𝐂-𝐍𝐂𝐂))

Proof 121 We prove that the invariant is valid for any digraph G. First notice that for an operational behaviour, since we cannot assume that PropositionΒ 55 (i.e., 𝐍𝐂𝐂(G)≀𝐍𝐒𝐂𝐂(G)) was already triggered, we use the max operator. But since any strongly connected component is connected, then 𝐍𝐒𝐂𝐂(G)-𝐍𝐂𝐂(G) is never negative. Consequently we only show by induction on 𝐍𝐒𝐂𝐂(G) that 𝐍𝐀𝐑𝐂(G)β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-min(𝐍𝐂𝐂(G),𝐍𝐒𝐂𝐂(G)-𝐍𝐂𝐂(G)). To begin notice that if X is a strongly (non void) connected component then either 𝐍𝐀𝐑𝐂(G[X])β‰₯|X| or 𝐍𝐀𝐑𝐂(G[X])=0 and in this latter case we have that both |X|=1 and X is strictly included in a connected component of G (recall that isolated vertices are not allowed). Thus we can directly assume that 𝐍𝐒𝐂𝐂(G)=k>1.

First, consider that there exists a connected component of G, say X, which is also strongly connected. Let G ' =G-X, consequently we have 𝐍𝐒𝐂𝐂(G ' )=𝐍𝐒𝐂𝐂(G)-1, 𝐍𝐂𝐂(G ' )=𝐍𝐂𝐂(G)-1, 𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G ' )=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-|X|, and 𝐍𝐀𝐑𝐂(G)β‰₯|X|+𝐍𝐀𝐑𝐂(G ' ). Then 𝐍𝐀𝐑𝐂(G)β‰₯|X|+𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G ' )-min(𝐍𝐂𝐂(G ' ),𝐍𝐒𝐂𝐂(G ' )-𝐍𝐂𝐂(G ' )) and thus 𝐍𝐀𝐑𝐂(G)β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-min(𝐍𝐂𝐂(G)-1,𝐍𝐒𝐂𝐂(G)-𝐍𝐂𝐂(G)), which immediately gives the result.

Second consider that any strongly connected component is strictly included in a connected component of G. Then, either there exists a strongly connected component X such that |X|β‰₯2. Let G ' =G-X, consequently we have 𝐍𝐒𝐂𝐂(G ' )=𝐍𝐒𝐂𝐂(G)-1, 𝐍𝐂𝐂(G ' )=𝐍𝐂𝐂(G), 𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G ' )=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-|X|, and 𝐍𝐀𝐑𝐂(G)β‰₯|X|+1+𝐍𝐀𝐑𝐂(G ' ). Then 𝐍𝐀𝐑𝐂(G)β‰₯|X|+1+𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G ' )-min(𝐍𝐂𝐂(G ' ),𝐍𝐒𝐂𝐂(G ' )-𝐍𝐂𝐂(G ' )) and thus 𝐍𝐀𝐑𝐂(G)β‰₯𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)+1-min(𝐍𝐂𝐂(G),𝐍𝐒𝐂𝐂(G)-𝐍𝐂𝐂(G)+1), which immediately gives the result. Or, all the strongly connected components are reduced to one element, so we have 𝐍𝐒𝐂𝐂(G)=𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G), and thus we obtain that 𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-min(𝐍𝐂𝐂(G),𝐍𝐒𝐂𝐂(G)-𝐍𝐂𝐂(G))=min(𝐍𝐂𝐂(G),𝐍𝐕𝐄𝐑𝐓𝐄𝐗(G)-𝐍𝐂𝐂(G)), which gives the result by for example PropositionΒ 99Β (143).

This bound is tight: take for example any circuit.

Proposition 122

𝐍𝐀𝐑𝐂≀𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2 -ππ•π„π‘π“π„π—Β·ππ’πŽπ”π‘π‚π„-ππ•π„π‘π“π„π—Β·ππ’πˆππŠ+ππ’πŽπ”π‘π‚π„Β·ππ’πˆππŠ

Proof 122 Since the maximum number of arcs of a digraph is 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 2 , and since:

  • No vertex can have a source as a successor we lose ππ•π„π‘π“π„π—Β·ππ’πŽπ”π‘π‚π„ arcs,

  • No sink can have a successor we lose ππ•π„π‘π“π„π—Β·ππ’πˆππŠ arcs.

In these two sets of arcs we count twice the arcs from the sinks to the sources, so we finally get a maximum number of arcs corresponding to the right -hand side of the inequality to prove.