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\text{(}\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,\mathrm{\Delta },\delta ,\lambda )$ and $(p,\mathrm{\Delta },\delta ,\kappa )$ realizability, where $\mathrm{\Delta }$ denotes the maximum degree for all vertices in a graph and $\lambda$ denotes the edge connectivity of a graph.