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

Abstract

It is widely recognized that certain graph-theoretic extremal questions play a major role in the study of communication network vulnerability. These extremal problems are special cases of questions concerning the realizability of graph invariants. We define a CS($p,q,\lambda ,\delta$) graph as a connected, separable graph having $p$ points, $q$ lines, line connectivity $\lambda$ and minimum degree $\delta$. In this notation, if the “CS” is omitted the graph is not necessarily connected and separable. An arbitrary quadruple of integers $(a,b,c,d)$ is called CS($p,q,A,5$) realizable if there is a CS($p,q,\lambda ,\delta$) graph with $p=a,q=b,\lambda =c$ and $\delta =d$. Necessary and sufficient conditions for a quadruple to be CS($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 }),(p,q,\lambda ,\delta )$ and $(p,q,\kappa ,\delta )$ realizability, where $A$ 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.