Realizability of $p$-Point, $q$-Line Graphs with Prescribed Maximum Degree, and Point Connectivity

Abstract

It is well known that some graph-theoretic extremal questions play a significant role in the investigation of communication network vulnerability. Answering questions concerning the realizability of graph invariants also solves several of these extremal problems. We define a $(p,q,\kappa ,\mathrm{\Delta })$ graph as a graph having $p$ points, $q$ lines, point connectivity $\kappa$ and maximum degree $\mathrm{\Delta }$. An arbitrary quadruple of integers $(a,b,c,d)$ is called $(p,q,\kappa ,\mathrm{\Delta })$ realizable if there is a $(p,q,\kappa ,\mathrm{\Delta })$ graph with $p=a,q=b,\kappa =c$ and $\mathrm{\Delta }=d$. Necessary and sufficient conditions for a quadruple to be $(p,q,\kappa ,\mathrm{\Delta })$ realizable are derived. In earlier papers, Boesch and Suffel gave necessary and sufficient conditions for $(p,q,\kappa )$, $(p,q,\lambda )$, $(p,q,\delta )$, $(p,\mathrm{\Delta },\delta ,\lambda )$ and $(p,\mathrm{\Delta },\delta ,\kappa )$ realizability, where $\lambda$ denotes the line connectivity of a graph and $\delta$ denotes the minimum degree for all points in a graph.