Premium
Realizability of p ‐point, q ‐line graphs with prescribed point connectivity, line connectivity, or minimum degree
Author(s) -
Boesch F. T.,
Suffel C. L.
Publication year - 1982
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/net.3230120311
Subject(s) - realizability , combinatorics , mathematics , degree (music) , graph , line graph , discrete mathematics , connectivity , algorithm , physics , acoustics
It is well known that certain graph‐theoretic extremal questions play a central role in the study of information network vulnerability. These extremal problems are special cases of the general question of realizability of graph invariants. For example a ( p , Δ, δ, λ) graph is 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 were recently given by the authors. In another manuscript they gave the solution to ( p , Δ, δ, k ) realizability, where k denotes the point connectivity. In this work we give necessary and sufficient conditions for ( p, q, k ), ( p, q , γ), and ( p, q , δ) realizability, where q denotes the number of lines of a graph.