The excessive [3]-index of all graphs

David Cariolaro*, Hung-Lin Fu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Let m be a positive integer and let G be a graph. A set M of matchings of G, all of which of size m, is called an [m]-covering of G if U M = E(G). G is called [m]-coverable if it has an [m]-covering. An [m]-covering M such that |M| is minimum is called an excessive [m]-factorization of G and the number of matchings it contains is a graph parameter called excessive [m]-index and denoted by x́ [m](G) (the value of x́ [m](G) is conventionally set to x́ if G is not [m]-coverable). It is obvious that x́ [1](G) = |E(G)| for every graph G, and it is not difficult to see that x́ [2](G) = max{x́(G), x́|E(G)|/2x́} for every [2]-coverable graph G. However the task of determining x́ [m](G) for arbitrary m and G seems to increase very rapidly in difficulty as m increases, and a general formula for m≥ 3 is unknown. In this paper we determine such a formula for m = 3, thereby determining the excessive [3]-index for all graphs.

Original languageEnglish
Article numberR124
JournalElectronic Journal of Combinatorics
Volume16
Issue number1
DOIs
StatePublished - 5 Oct 2009

Keywords

  • Edge coloring
  • Excessive [m]-factorization
  • Excessive [m]-index
  • Matching

Fingerprint Dive into the research topics of 'The excessive [3]-index of all graphs'. Together they form a unique fingerprint.

Cite this