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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 363-370 |
| Number of pages | 8 |
| Journal | Journal of Graph Theory |
| Volume | 4 |
| Issue number | 4 |
| DOIs | |
| State | Published - Jan 1 1980 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Geometry and Topology
Cite this
}
Realizability of p‐point graphs with prescribed minimum degree, maximum degree, and line connectivity. / Boesch, F. T.; Suffel, Charles.
In: Journal of Graph Theory, Vol. 4, No. 4, 01.01.1980, p. 363-370.Research output: Contribution to journal › Article
TY - JOUR
T1 - Realizability of p‐point graphs with prescribed minimum degree, maximum degree, and line connectivity
AU - Boesch, F. T.
AU - Suffel, Charles
PY - 1980/1/1
Y1 - 1980/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0002619685&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0002619685&partnerID=8YFLogxK
U2 - https://doi.org/10.1002/jgt.3190040404
DO - https://doi.org/10.1002/jgt.3190040404
M3 - Article
VL - 4
SP - 363
EP - 370
JO - Journal of Graph Theory
JF - Journal of Graph Theory
SN - 0364-9024
IS - 4
ER -