Realizability of \(p\)-Vertex, \(q\)-Edge Graphs with Prescribed Vertex Connectivity and Minimum Degree

Abstract

It is an established fact that some graph-theoretic extremal questions play an important part in the investigation of communication network vulnerability. Questions concerning the realizability of graph invariants are generalizations of the extremal problems. We define a \((p,q, \kappa,\delta)\) graph as a graph having \(p\) vertices, \(q\) edges, vertex connectivity \(\kappa\) and minimum degree \(\delta\). An arbitrary quadruple of integers \((a,b, c, d)\) is called \((p,q, \kappa, \delta)\) realizable if there is a \((p,q, \kappa, \delta)\) graph with \(p=a, q=b, \kappa=c$ and \(\delta=d\). Necessary and sufficient conditions for a quadruple to be \((p,q, \kappa, \delta)\) realizable are derived. In earlier papers, Boesch and Suffel gave necessary and sufficient conditions for \((p,q, \kappa), (p,q, \lambda), (p,4, \delta), (p, \Delta,\delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability, where \(\Delta\) denotes the maximum degree for all vertices in a graph and \(\lambda\) denotes the edge connectivity of a graph.