A note on the cycle multiplicity of line-graphs and total graphs

AbstractThe cycle multiplicity π̄2′(G) of a graph G, as defined by Chartrand, Geller, and Hedetniemi [1], is the maximum number of line-disjoint cycles contained in G. Denote by [x] the greatest integer less than or equal to x, by | S | the cardinality of the set S, by E(G) the edge set of G, by Ge the subgraph induced by the vertices of even degree in G, and by Kp the complete graph on p vertices. We proved the following results: If G is a forest then π2′[L(G)]=∑i[deg(vi)3[deg(vi)−12]], π2′[T(G)]=|E(G)|+∑i[deg(vi)3[deg(vi)−12]], the summation being over all vertices of G. If G has cycles, then the right members of the preceding equalities added to π̄2′(Ge) give lower bounds for the left members. If G ≡ Kp, then π2′[L(G)]=(p3) and π2′[T(G)]=(p+13)