Premium
Linear arboricity for graphs with multiple edges
Author(s) -
Aïtdjafer Houria
Publication year - 1987
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.3190110203
Subject(s) - arboricity , combinatorics , mathematics , multiplicity (mathematics) , graph , dense graph , simple graph , discrete mathematics , degree (music) , 1 planar graph , line graph , planar graph , physics , geometry , acoustics
Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ( G ), the linear arboricity la(G) satisfies ⌈Δ( G )/2⌉ ≦ la(G) ≦ ⌈(Δ( G ) + 1)/2⌉. Here it is proved that if G is a loopless graph with maximum degree Δ( G ) ≦ k and maximum edge multiplicity μ( G) ≦ k − 2 n +1 + 1, where k ≧ 2 n −2 , then la(G) ≦ k − 2 n . It is also conjectured that for any loopless graph G , ⌈Δ( G )/2⌉ ≦ la(G) ≦ ⌈(Δ( G ) + μ( G ))/2⌉.