Premium
Bounds for the vertex linear arboricity
Author(s) -
Matsumoto Makoto
Publication year - 1990
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/jgt.3190140113
Subject(s) - arboricity , combinatorics , mathematics , vertex (graph theory) , degeneracy (biology) , bound graph , graph , vertex connectivity , induced subgraph , upper and lower bounds , discrete mathematics , graph power , planar graph , line graph , biology , bioinformatics , mathematical analysis
The vertex linear arboricity vla( G ) of a nonempty graph G is the minimum number of subsets into which the vertex set V(G) can be partitioned so that each subset induces a subgraph whose connected components are paths. This paper provides an upper bound for vla( G ) of a connected nonempty graph G , namely vla( G ) ≦ 1 + ⌊δ( G )/2⌋ where δ( G ) denotes the maximum degree of G . Moreover, if δ( G ) is even, then vla( G ) = 1 + ⌊δ( G )/2⌋ if and only if G is either a cycle or a complete graph.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom