✦ LIBER ✦

Graph decomposition with constraints on the minimum degree

✍ Scribed by John Sheehan

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 888 KB
Volume: 68
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90122-7

No coin nor oath required. For personal study only.

✦ Synopsis

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, rather than constraints on the minimum degree of G, guaranteeing such a partition are also discussed.

, [$d] ) there exists a partition (X, Y) of V(G) such that (i) (X) = [$nl +i, lYl= [$nj -i; (ii) 6(X) 3 [$Sl + i, 6(Y) 5 l;Sj -i; (iii) X E max( [in1 + i, G) or Y E max(

📜 SIMILAR VOLUMES

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

Graph Decompositions Satisfying Extremal

Graph Decompositions Satisfying Extremal Degree Constraints

✍ Paul A. Catlin 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB

## Abstract We show that the vertex set of any graph __G__ with __p__⩾2 vertices can be partitioned into non‐empty sets __V__~1~, __V__~2~, such that the maximum degree of the induced subgraph 〈__V__~i~〉 does not exceed where p^i^ = |__V__^i^|, for __i__=1, 2. Furthermore, the structure of the in

On decomposition of triangle-free graphs

On decomposition of triangle-free graphs under degree constraints

✍ Kaneko, Atsushi 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

We prove that if s and t are positive integers and if G is a triangle-free graph with minimum degree s + t, then the vertex set of G has a decomposition into two sets which induce subgraphs of minimum degree at least s and t, respectively.

Decomposition of bipartite graphs under

Decomposition of bipartite graphs under degree constraints

✍ H. J. Broersma; R. J. Faudree; J. Den Van Heuvel; H. J. Veldman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 339 KB

## Abstract Let __G__ = __(A, B; E)__ be a bipartite graph. Let __e__~1~, __e__~2~ be nonnegative integers, and __f__~1~, __f__~2~ nonnegative integer‐valued functions on __V(G)__ such that __e__~__i__~ ≦ |__E__| ≦ __e__~1~ + __e__~2~ and __f~i~(v)__ ≦ __d(v)__ ≦ __f__~1~__(v)__ + __f__~2~__(v)__ f

On graphs with equal edge-connectivity a

On graphs with equal edge-connectivity and minimum degree

✍ Donald L. Goldsmith; Arthur T. White 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 599 KB

It was proved by Chartrand f hat if G is a graph of order p for which the minimum degree is at least [&I, then the edge-connectivity of G equals the minimum degree of G. It is shown here that one may allow vertices of degree less than $p and still obtain the same conclusion, provided the degrees are