On the excessive [m]-index of a tree

DOI10.1016/J.DAM.2013.08.014MaRDI QIDQ741745zbMATH OpenOpenAlexFDO

Authors G. Mazzuoccolo

Publication date 12 September 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.1521

zbMATH Keywords

treesmatchingsexcessive indexcaterpillars

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The excessive [m]-index of a graph G is the minimum number of matchings of size m needed to cover the edge-set of G. We call a graph G [m]-coverable if its excessive [m]-index is finite. Obviously the excessive [1]-index is |E(G)| for all graphs and it is an easy task the computation of the excessive [2]-index for a [2]-coverable graph. The case m=3 is completely solved by Cariolaro and Fu in 2009. In this paper we prove a general formula to compute the excessive [4]-index of a tree and we conjecture a possible generalization for any value of m. Furthermore, we prove that such a formula does not work for the excessive [4]-index of an arbitrary graph.

Recommendations

• The excessive [3]-index of all graphs
• Covering graphs with matchings of fixed size
• Excessive \([l, m]\)-factorizations
• On the complexity of computing the excessive \([B]\)-index of a graph
• Covering cubic graphs with matchings of large size

Cites work

• scientific article; zbMATH DE number 5130724 (Why is no real title available?)
• scientific article; zbMATH DE number 3378938 (Why is no real title available?)
• 1-factor covers of regular graphs
• An upper bound for the excessive index of an \(r\)-graph
• Blocking and anti-blocking pairs of polyhedra
• Covering cubic graphs with matchings of large size
• Covering graphs with matchings of fixed size
• Excessive factorizations of bipartite multigraphs
• Graphs of arbitrary excessive class
• Matching theory
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On parsimonious edge-colouring of graphs with maximum degree three
• The Solution of a Timetabling Problem
• The equivalence of two conjectures of Berge and Fulkerson
• The excessive [3]-index of all graphs

Cited in

(7)

• On excessive index of certain networks
• Graphs of arbitrary excessive class
• Excessive \([l, m]\)-factorizations
• The excessive [3]-index of all graphs
• Covering graphs with matchings of fixed size
• On the complexity of computing the excessive \([B]\)-index of a graph
• Excessive index for mesh derived networks

This page was built for publication: On the excessive \([m]\)-index of a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741745)