✦ LIBER ✦

Balanced graphs with edge density constraints

✍ Scribed by John Sheehan

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 400 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140607

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Suppose that G is a finite simple graph with |V(G)| = 2__n__ (n ≠ 3). a partition (X,Y) of V(G) is balanced if

(i) |X| = |Y| = n,

(ii) δ(X) ≥ 1, δ(Y) ≥ 1.

Where δ(X) is the minimum degree of the induced subgraph 〈X〉 with vertex set X.

We prove that if |E(G)| ≥ (n^2^ + n + 2)/2 and G is connected, then G contains a balanced partition. The result is sharp.

📜 SIMILAR VOLUMES

Balanced graphs with minimum degree cons

Balanced graphs with minimum degree constraints

✍ John Sheehan 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 464 KB

Sheehan, J., Balanced graphs with minimum degree constraints, Discrete Mathematics 102 (1992) 307-314. Let G be a finite simple graph on n vertices with minimum degree 6 = 6(G) (n = 6 (mod 2)). Suppose that 0 < 6 c n -2, 06 i 4 [?Sl. A partition (x, Y) of V(G) is said to be an (i, a)-partition of G

On 4-critical planar graphs with high ed

On 4-critical planar graphs with high edge density

✍ Gerhard Koester 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 236 KB

Koester, G., On 4-critical planar graphs with high edge density, Discrete Mathematics 98 (1991) 147-151.

Partitioning graph matching with constra

Partitioning graph matching with constraints

✍ Richard E. Blake 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 420 KB

Sphere of influence graphs: Edge density

Sphere of influence graphs: Edge density and clique size

✍ T.S. Michael; T. Quint 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 444 KB

Edge density and independence ratio in t

Edge density and independence ratio in triangle-free graphs with maximum degree three

✍ Jerrold Griggs; Owen Murphy 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 548 KB

A simple polynomial-time algorithm is presented which computes independent sets of guaranteed size in connected triangle-free noncubic graphs with maximum degree 3. Let nand m denote the number of vertices and edges, respectively, and let c '= m/n denote the edge density where c < 3/2. The algorithm

Graphs with edge-preserving majority fun

Graphs with edge-preserving majority functions

✍ Hans-Jürgen Bandelt 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 319 KB

A majority function m is a ternary operation satisfying the identity m(u, U, u) = m(u, u, u) = m(u, u, u) = u. It is shown that a finite graph G admits an edge-preserving majority function on its vertex set if and only if G is an absolute retract of bipartite graphs. This parallels previous results