Realizability ofp-point,q-line graphs with prescribed maximum degree and line connectivity or minimum degree
David DiMarco · Networks · 2000
We define a (p, q, λ, Δ) graph as a graph having p points, q lines, line connectivity λ, and maximum degree Δ. An arbitrary quadruple of integers (a, b, c, d) is called (p, q, λ, Δ) realizable if there is a (p, q, λ, Δ) graph with p = a, q = b, λ = c, and Δ = d. In this work, necessary and sufficient conditions for (p, q, λ, Δ) and (p, q, δ, Δ) realizability are derived, where δ denotes the minimum degree of a graph. In earlier papers, Boesch and Suffel gave necessary and sufficient conditions for (p, q, κ), (p, q, λ), (p, q, δ), (p, Δ, δ λ), and (p, Δ, δ κ) realizability, where κ denotes the point connectivity of a graph. © 2000 John Wiley & Sons, Inc.