𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimallyk-Edge-Connected Directed Graphs of Maximal Size

✍ Scribed by Alex R. Berg; Tibor Jordán

Publisher
Springer Japan
Year
2005
Tongue
English
Weight
352 KB
Volume
21
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Sufficient conditions for graphs to be λ
Sufficient conditions for graphs to be λ′-optimal, super-edge-connected, and maximally edge-connected
✍ Angelika Hellwig; Lutz Volkmann 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB

## Abstract The restricted‐edge‐connectivity of a graph __G__, denoted by λ′(__G__), is defined as the minimum cardinality over all edge‐cuts __S__ of __G__, where __G__‐__S__ contains no isolated vertices. The graph __G__ is called λ′‐optimal, if λ′(__G__) = ξ(__G__), where ξ(__G__) is the minimum

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.

The maximal size of graphs with at most
The maximal size of graphs with at most k edge-disjoint paths connecting any two adjacent vertices
✍ Mao-cheng Cai 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 502 KB

Let n and k be positive integers satisfying k + 1 s n s 3k -1, and G a simple graph of order n and size e(G) with at most k edge-disjoint paths connecting any two adjacent vertices. In this paper we prove that e(G) s l(n + k)\*/8], and give complete characterizations of the extremal graphs and the e

Maximal chromatic polynomials of connect
Maximal chromatic polynomials of connected planar graphs
✍ Ioan Tomescu 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 429 KB 👁 1 views

## Abstract In this paper we obtain chromatic polynomials of connected 3‐ and 4‐chromatic planar graphs that are maximal for positive integer‐valued arguments. We also characterize the class of connected 3‐chromatic graphs having the maximum number of __p__‐colorings for __p__ ≥ 3, thus extending a

Super edge connectivity properties of co
Super edge connectivity properties of connected edge symmetric graphs
✍ Li, Qiaoliang; Li, Qiao 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 47 KB 👁 2 views

The super edge connectivity properties of a graph G can be measured by the restricted edge connectivity Ј(G). We evaluate Ј(G) and the number of i-cutsets C i (G), d Յ i Յ 2d Ϫ 3, explicitly for each d-regular edge-symmetric graph G. These results improve the previous one by R. Tindell on the same s