Realizability of p ‐point, q ‐line graphs with prescribed point connectivity, line connectivity, or minimum degree

It is well known that certain graph‐theoretic extremal questions play a central role in the study of information network vulnerability. These extremal problems are special cases of the general question of realizability of graph invariants. For example a ( p , Δ, δ, λ) graph is a graph having p ‐points, maximum degree Δ, minimum degree δ, and line‐connectivity λ. An arbitrary quadruple of integers ( a, b, c, d ) is called ( p , Δ, δ, γ) realizable if there is a ( p , Δ, δ, γ) graph with p = a , Δ = b , δ = c , and γ = d. Necessary and sufficient conditions for a quadruple to be ( p , Δ, δ, γ) realizable were recently given by the authors. In another manuscript they gave the solution to ( p , Δ, δ, k ) realizability, where k denotes the point connectivity. In this work we give necessary and sufficient conditions for ( p, q, k ), ( p, q , γ), and ( p, q , δ) realizability, where q denotes the number of lines of a graph.