✦ LIBER ✦

Balanced graphs with minimum degree constraints

✍ Scribed by John Sheehan

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 464 KB
Volume: 102
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90123-w

No coin nor oath required. For personal study only.

✦ Synopsis

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 if: (i) 1X1= [in] + i, IYI = l&J -i, (ii) 6((X))a [;Sl +i, B((Y))a [tsj -i. We prove that if G is connected then G possesses an (i, B)-partition for some i, 0 L i s [is] -1. We show that this result is sharp and provide a family of counterexamples to Conjecture 5 in Sheehan (1988).

📜 SIMILAR VOLUMES

Graph decomposition with constraints on

Graph decomposition with constraints on the minimum degree

✍ John Sheehan 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 888 KB

Let G be a finite simple graph on n vertices with minimum degree 6(G) 3 6 (n = 6 (mod 2)). Let max(k, G) denote the set of all k-subsets A E V(G) such that the number of edges in the induced subgraph (A) is a maximum. We prove that for some i E (0, 1.2, . . . ). Analogous edge density constraints, r

Graph decomposition with constraints on

Graph decomposition with constraints on the connectivity and minimum degree

✍ Carsten Thomassen 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

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

Balanced graphs with edge density constr

Balanced graphs with edge density constraints

✍ John Sheehan 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 400 KB

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

Subdivisions of graphs with large minimu

Subdivisions of graphs with large minimum degree

✍ Carsten Thomassen 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 1 views

Domination in graphs with minimum degree

Domination in graphs with minimum degree two

✍ William McCuaig; Bruce Shepherd 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 545 KB

The domination number y ( G ) of a graph G = (V E ) is the minimum cardinality of a subset of Vsuch that every vertex is either in the set or is adjacent to some vertex in the set. We show that if a connected graph G has minimum2degree two and is not one of seven exceptional graphs, then y ( g ) I ~

Decomposing graphs under degree constrai

Decomposing graphs under degree constraints

✍ Stiebitz, Michael 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB

We prove a conjecture of C. Thomassen: If s and t are non-negative integers, and if G is a graph with minimum degree s + t + 1, then the vertex set of G can be partitioned into two sets which induce subgraphs of minimum degree at least s and t , respectively.