Linear arboricity for graphs with multiple edges

✍ Scribed by Houria Aït-djafer

• Publisher: John Wiley and Sons
• Year: 1987
• Tongue: English
• Weight: 266 KB
• Volume: 11
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190110203

✦ Synopsis

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree A(G). the linear arboricity / a ( G ) satisfies rA(G)/21 5 /a(G) 5 r(A(G) + 11/21, Here it is proved that if G is a loopless graph with maximum degree A ( G ) S k and maximum edge multiplicity

1. Introduction

All terms not explicitly defined here may be found in IS]. For any real number

x . !XI denotes the integer part of x and r-rl = For a graph G. V ( G ) and E ( G ) denote the set of vertices and the set of edges of G. respectively. The degree d , ( v ) of a vertex v in G is the number of edges of C incident with 1 9 . We denote by 6(G) and A ( G ) the tnininiurn and maximum degrees, respectively, of vertices of G. The set of vertices of degree i in G is denoted by

V , ( G ) . The maximum number of edges joining two vertices in G is called the edge multiplicity of G and denoted by p ( G ) .

A linear foresr in a graph G is a subgraph of G, each component of which is a path. The linear arboricity h ( G ) of a graph G as defined by Harary in 18) is the minimum number of linear forests into which E ( G ) can be decomposed. Akiyama, Exoo, and Harary conjectured the following.

Conjecture 1 121. For any simple graph G with maximum degree A. we have