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

F. T. Boesch, Charles Suffel

Research output: Contribution to journalArticle

7 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)341-350
Number of pages10
JournalNetworks
Volume12
Issue number3
DOIs
StatePublished - Jan 1 1982

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Networks and Communications

Cite this

@article{03312cecb9504d5d83f3e09519ce35fc,
title = "Realizability of p‐point, q‐line graphs with prescribed point connectivity, line connectivity, or minimum degree",
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.",
author = "Boesch, {F. T.} and Charles Suffel",
year = "1982",
month = "1",
day = "1",
doi = "https://doi.org/10.1002/net.3230120311",
language = "English (US)",
volume = "12",
pages = "341--350",
journal = "Networks",
issn = "0028-3045",
publisher = "Wiley-Liss Inc.",
number = "3",

}

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

In: Networks, Vol. 12, No. 3, 01.01.1982, p. 341-350.

Research output: Contribution to journalArticle

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 -