Abstract
Let k and n be positive integers. Let G be a graph of order n≤4k, and let n = ∑ki=1 ai be a partition of n into k positive integers ai with 1≤ai≤4. In Matsunaga (Preprint, 1995) one of the authors proved that if G is 2-connected and the minimum degree of G is at least k, then with certain types of exceptions being allowed, the vertex set of G can be decomposed into k disjoint subsets Al,...,Ak so that |Ai| = ai and "the subgraph induced by Ai is connected" for all i, 1≤i≤k. In the present paper we extend this result for connected graphs in general. The paper also features the existence of D3-paths with a prescribed endvertex in a graph. (A D3-path in a graph is a path of the graph whose removal leaves no component of order at least 3.)
| Original language | English |
|---|---|
| Pages (from-to) | 87-104 |
| Number of pages | 18 |
| Journal | Discrete Mathematics |
| Volume | 213 |
| Issue number | 1-3 |
| DOIs | |
| Publication status | Published - 2000 Feb 28 |
| Event | Selected Topics in Discrete Mathematics - Warsaw, Poland Duration: 1996 Aug 26 → 1996 Sept 28 |
Keywords
- D-path
- Graph decomposition
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
Fingerprint
Dive into the research topics of 'Graph decompositions and D3-paths with a prescribed endvertex'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS