Realizability of p-point graphs with prescribed minimum degree, maximum degree, and line connectivity

✍ Scribed by F. T. Boesch; C. L. Suffel

• Publisher: John Wiley and Sons
• Year: 1980
• Tongue: English
• Weight: 316 KB
• Volume: 4
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190040404

✦ Synopsis

Abstract

It is well known that certain graph‐theoretic extremal questions play a central role in the study of communication network vulnerability. Herein we consider a generalization of some of the classical results in this area. We define a (p, Δ, δ, λ) graph as a graph having p points, maximum degree Δ, minimum degree Δ, and line connectivity λ. An arbitrary quadruple of integers (a, b, c, d) is called (p, Δ, δ, λ) realizable if there is a (p, Δ, δ, λ) graph with p = a, Δ = b, Δ = c, and λ = d. Necessary and sufficient conditions for a quadruple to be (p, Δ, δ, λ) realizable are derived.