Premium
On linear vertex‐arboricity of complementary graphs
Author(s) -
Alavi Yousef,
Liu Jiuqiang,
Wang Jianfang
Publication year - 1994
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.3190180309
Subject(s) - arboricity , combinatorics , mathematics , vertex (graph theory) , degeneracy (biology) , graph , bound graph , discrete mathematics , graph power , line graph , planar graph , bioinformatics , biology
The linear vertex‐arboricity ρ( G ) of a graph G is defined to be the minimum number of subsets into which the vertex set of G can be partitioned such that each subset induces a linear forest. In this paper, we give the sharp upper and lower bounds for the sum and product of linear vertex‐arboricities of a graph and its complement. Specifically, we prove that for any graph G of order p .and for any graph G of order p = (2 n + 1) 2 , where n ≅ Z + , 2 n + 2 ≦ ρ( G ) + ρ( G ).