Premium
Graph decompositions without isolated vertices III
Author(s) -
Enomoto Hikoe,
Matsunaga Shinsuke
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199702)24:2<155::aid-jgt3>3.0.co;2-p
Subject(s) - combinatorics , mathematics , partition (number theory) , disjoint sets , path graph , frequency partition of a graph , bound graph , vertex (graph theory) , graph , induced subgraph , wheel graph , degree (music) , discrete mathematics , graph power , line graph , physics , acoustics
Let G be a graph of order n , and n = Σ k i =1 a i be a partition of n with a i ≥ 2. In this article we show that if the minimum degree of G is at least 3 k −2, then for any distinct k vertices v 1 ,…, v k of G , the vertex set V(G) can be decomposed into k disjoint subsets A 1 ,…, A k so that | A i | = a i ,v i is A i is an element of A i and “the subgraph induced by A i contains no isolated vertices” for all i , 1 ≥ i ≥ k . Here, the bound on the minimum degree is sharp. © 1997 John Wiley & Sons, Inc.