Realizability of p ‐point graphs with prescribed minimum degree, maximum degree, and line connectivity

It is well known that certain graph‐theoretic extremal questions play a central role in the study of communication network vulnerability. Herein we consider a generalization of some of the classical results in this area. We define a ( p , Δ, δ, λ) graph as 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 are derived.