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, \lambda, \delta)\) 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, \Delta)\), \((p, q, \lambda,\Delta )\), \((p, q, \delta, \Delta)\), \((p, q, \lambda, \delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(\Delta\) denotes the maximum degree for all points in a graph and \(\kappa\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa)\), \((p, q, \lambda)\), \((p, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.