Realizability of p‐point graphs with prescribed minimum degree, maximum degree, and line connectivity

F. T. Boesch, Charles Suffel

Research output: Contribution to journalArticle

11 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)363-370
Number of pages8
JournalJournal of Graph Theory
Volume4
Issue number4
DOIs
StatePublished - Jan 1 1980

Fingerprint

Realizability
Minimum Degree
Maximum Degree
Connectivity
Quadruple
Line
Graph in graph theory
Vulnerability
Communication Networks
Necessary Conditions
Integer
Sufficient Conditions
Arbitrary

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Cite this

@article{0fadda073e0e4567bfb98aa21b9bb622,
title = "Realizability of p‐point graphs with prescribed minimum degree, maximum degree, and line connectivity",
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.",
author = "Boesch, {F. T.} and Charles Suffel",
year = "1980",
month = "1",
day = "1",
doi = "https://doi.org/10.1002/jgt.3190040404",
language = "English (US)",
volume = "4",
pages = "363--370",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "4",

}

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 journalArticle

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 -