✦ LIBER ✦

Subgraphs and Their Degree Sequences of a Digraph

✍ Scribed by Wai-Kai Chen

Publisher: Elsevier Science
Year: 1980
Tongue: English
Weight: 912 KB
Volume: 310
Category: Article
ISSN: 0016-0032
DOI: 10.1016/0016-0032(80)90013-7

No coin nor oath required. For personal study only.

✦ Synopsis

7'he paper presents general conditions that are necessary and suficient for the existence of a (p, s) subgraph with prescribed degrees of a given digraph. It is shown that the subgraph problem of a digraph, the degree sequence problem of a digraph, the subgraph problem of a graph and the degree sequence problem of a graph can all be treated in a systematic way, thus allowing the unification of many of existing results and providing an insight into the more complicated cases.

📜 SIMILAR VOLUMES

Machine sequencing: Disjunctive graphs a

Machine sequencing: Disjunctive graphs and degree-constrained subgraphs

✍ Egon Balas 📂 Article 📅 1970 🏛 John Wiley and Sons 🌐 English ⚖ 578 KB

Graph classes characterized both by forb

Graph classes characterized both by forbidden subgraphs and degree sequences

✍ Michael D. Barrus; Mohit Kumbhat; Stephen G. Hartke 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB

## Abstract Given a set ${\cal F}$ of graphs, a graph __G__ is ${\cal F}$‐free if __G__ does not contain any member of ${\cal F}$ as an induced subgraph. We say that ${\cal F}$ is a degree‐sequence‐forcing set if, for each graph __G__ in the class ${\cal C}$ of ${\cal F}$‐free graphs, every realiza

Degree sequence conditions for maximally

Degree sequence conditions for maximally edge-connected graphs and digraphs

✍ Dankelmann, Peter; Volkmann, Lutz 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB 👁 2 views

In this paper we give simple degree sequence conditions for the equality of edge-connectivity and minimum degree of a (di-)graph. One of the conditions implies results by Bollobás, Goldsmith and White, and Xu. Moreover, we give analogue conditions for bipartite (di-)graphs.

A survey of sequences of central subgrap

A survey of sequences of central subgraphs

✍ Slater, Peter J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB

Because vertices most central with respect to the center (minimax distance) criterion and the median (minisum distance) criterion can be arbitrarily far apart even in trees, several sequences of central sets have been introduced. Each such sequence is based on an underlying concept that shows the ce

Subgraphs with restricted degrees of the

Subgraphs with restricted degrees of their vertices in planar graphs

✍ Igor Fabrici; Stanislav Jendrol' 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 335 KB

We prove that every 3-connected planar graph G of order at least k contains a connected subgraph H on k vertices each of which has degree (in G) at most 4k + 3, the bound 4k + 3 being best possible. (~

Interchange Theorems for Hypergraphs and

Interchange Theorems for Hypergraphs and Factorization of Their Degree Sequences

✍ A.A. Chernyak 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 124 KB

The aim of this paper is to unify interchange theorems and extend them to hypergraphs. To this end sufficient conditions for equality of the l 1 -distance between equivalence classes and the l 1 -distance between corresponding order-type functions are provided. The generality of this result is demon