✦ LIBER ✦

Graph decomposition with constraints on the connectivity and minimum degree

✍ Scribed by Carsten Thomassen

Publisher: John Wiley and Sons
Year: 1983
Tongue: English
Weight: 145 KB
Volume: 7
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190070204

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For each pair s,t of natural numbers there exist natural numbers f(s,t) and g(s,t) such that the vertex set of each graph of connectivity at least f(s,t) (respectively minimum degree at least g(s,t)) has a decomposition into sets which induce subgraphs of connectivity (respectively minimum degree) at least s and t, respectively.

📜 SIMILAR VOLUMES

Realizability of p-point graphs with pre

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

✍ F. T. Boesch; C. L. Suffel 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 316 KB

## 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,

Realizability of p-point, q-line graphs

Realizability of p-point, q-line graphs with prescribed maximum degree and line connectivity or minimum degree

✍ D. DiMarco 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 74 KB 👁 3 views

Degree sequence conditions for equal edg

Degree sequence conditions for equal edge-connectivity and minimum degree, depending on the clique number

✍ Lutz Volkmann 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 87 KB

## Abstract Using the well‐known Theorem of Turán, we present in this paper degree sequence conditions for the equality of edge‐connectivity and minimum degree, depending on the clique number of a graph. Different examples will show that these conditions are best possible and independent of all the

The minimum order of a cayley graph with

The minimum order of a cayley graph with given degree and diameter

✍ Yahya Ould Hamidoune 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB

On the complexity of distributed graph c

On the complexity of distributed graph coloring with local minimality constraints

✍ Cyril Gavoille; Ralf Klasing; Adrian Kosowski; Łukasz Kuszner; Alfredo Navarra 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

On the Inapproximability of Disjoint Pat

On the Inapproximability of Disjoint Paths and Minimum Steiner Forest with Bandwidth Constraints

✍ Bin Ma; Lusheng Wang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 230 KB

In this paper, we study the inapproximability of several well-known optimization problems in network optimization. We show-that the max directed vertex-disjoint paths problem cannot be approximated within ratio 2 log 1&= n unless NP DTIME[2 polylog n ], the max directed edge-disjoint paths problem c