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

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 these extremal problems. We define a $(p,q,\lambda ,\delta )$ graph as a graph having $p$ points, $q$ lines, line connectivity $\lambda$ and minimum degree $\delta$. An arbitrary quadruple of integers $(a,b,c,d)$ is called $(p,q,\lambda ,\delta )$ realizable if there is a $(p,q,\lambda ,\delta )$ graph with $p=a,q=b,\lambda =c$, and $\delta =d$. Inequalities representing necessary and sufficient conditions for a quadruple to be $(p,q,\lambda ,\delta )$ realizable are derived. In recent papers, the author gave necessary and sufficient conditions for $(p,q,\kappa ,\mathrm{\Delta }),(p,q,\lambda ,\mathrm{\Delta }),(p,q,\delta ,\mathrm{\Delta })$ and $(p,q,\kappa ,\delta )$ realizability, where $\mathrm{\Delta }$ denotes the maximum degree for all points in a graph and $\lambda$ denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for $(p,q,\kappa ),(p,q,\lambda ),(p,q,\delta ),(p,\mathrm{\Delta },\delta ,\lambda )$ and $(p,\mathrm{\Delta },\delta ,\kappa )$ realizability in earlier manuscripts.