Graph partition into paths containing specified vertices
type: Item
instance of: scholarly article
title: Graph partition into paths containing specified vertices
zbMATH Open document ID: 0990.05103
DOI: 10.1016/S0012-365X(01)00349-1
author: Ken-ichi Kawarabayashi
published in: Discrete Mathematics
publication date: 2002-05-28T00:00:00Z
review text: Let \(G\) be a graph of order \(n\), and let \(\sigma_2(G)\) be the minimum degree sum of a pair of nonadjacent vertices. Recently, Enomoto and Ota conjectured that, if a partition \(n=\sum_{i=1}^k a_i\) is given and \(\sigma_2(G)\geq n+k-1\), then for any \(k\) distinct vertices \(v_1,v_2,\ldots,v_k\), the graph \(G\) can be decomposed into vertex-disjoint paths \(P_1,P_2,\ldots,P_k\) such that \(|V(P_i)|=a_i\) and \(v_i\) is an endvertex of \(P_i\) for \(i=1,2,\ldots,k\). Enomoto and Ota verified their conjecture for \(k\leq 3\) or \(a_i\leq 5\) for all \(i\). In this paper, the author proves this conjecture under the stronger assumption that \(\sigma_2(G)\geq\sum_{i=1}^k\max(\lfloor 4a_i/3\rfloor,a_i+1)-1\).
reviewed by: Lutz Volkmann
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1746267
zbMATH Keywords: graph partition
zbMATH Keywords: paths containing specified vertices
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00349-1
OpenAlex ID: W2127148245
description: scientific article; zbMATH DE number 1746267