Two families of graphs satisfying the cycle basis interpolation property

✍ Scribed by Elzbieta B. Jarrett

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 353 KB
• Volume: 84
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(90)90271-i

✦ Synopsis

The length of a cycle basis of a graph G is the sum of the lengths of its cycles. Let C, c+ be the lengths of the minimal and maximal cycle basis, respectively.

Then G has the cycle basis interpolation property (chip) if for all integers c, c-CC CC+, there exists a cycle basis of length c. We construct two families of graphs with the chip, namely snake-graphs and kite-graphs. Lemma 1.1 [2]. Zf m cycles %' = {CI, Cl, . . . , CL} generate all cycles of some cycle basis % = {C,, Cz, . . . , C,,,}, then %" is also a cycle basis.