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, \Delta)\) graph as a graph having \(p\) points, \(q\) lines, point connectivity \(\kappa\) and maximum 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 \(\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, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \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.