### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 341-350 |

Number of pages | 10 |

Journal | Networks |

Volume | 12 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1982 |

### All Science Journal Classification (ASJC) codes

- Information Systems
- Computer Networks and Communications

### Cite this

}

*Networks*, vol. 12, no. 3, pp. 341-350. https://doi.org/10.1002/net.3230120311

**Realizability of p‐point, q‐line graphs with prescribed point connectivity, line connectivity, or minimum degree.** / Boesch, F. T.; Suffel, Charles.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Realizability of p‐point, q‐line graphs with prescribed point connectivity, line connectivity, or minimum degree

AU - Boesch, F. T.

AU - Suffel, Charles

PY - 1982/1/1

Y1 - 1982/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84987047387&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84987047387&partnerID=8YFLogxK

U2 - https://doi.org/10.1002/net.3230120311

DO - https://doi.org/10.1002/net.3230120311

M3 - Article

VL - 12

SP - 341

EP - 350

JO - Networks

JF - Networks

SN - 0028-3045

IS - 3

ER -