Premium
Realizability of p ‐point, q ‐line graphs with prescribed maximum degree and line connectivity or minimum degree
Author(s) -
DiMarco D.
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200008)36:1<64::aid-net7>3.0.co;2-r
Subject(s) - realizability , combinatorics , degree (music) , mathematics , graph , discrete mathematics , line graph , line (geometry) , algorithm , physics , geometry , acoustics
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.