On the excessive [m]-index of a tree

DOI10.1016/J.DAM.2013.08.014zbMATH Open1300.05062arXiv1301.1521OpenAlexW1982683179MaRDI QIDQ741745FDOQ741745

Authors: G. Mazzuoccolo 

Publication date: 12 September 2014

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

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.

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

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

zbMATH Keywords

treesmatchingsexcessive indexcaterpillars

Mathematics Subject Classification ID

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

Cites Work

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

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)