The tree number of a graph with a given girth

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

A family of subtrees of a graph G whose edge sets form a partition of the edge set of G is called a tree decomposition of G. The minimum number of trees in a tree decomposition of G is called the tree number of G and is denoted by τ(G). It is known that if G is connected then τ(G) ≤ ⌈|G|/2⌉. In this paper we show that if G is connected and has girth g ≥ 5 then τ(G) ≤ ⌊|G|/g⌋ + 1. Surprisingly, the case when g = 4 seems to be more difficult. We conjecture that in this case τ(G) ≤ ⌊|G|/4⌋ + 1 and show a wide class of graphs that satisfy it. Also, some special graphs like complete bipartite graphs and n-dimensional cubes, for which we determine their tree numbers, satisfy it. In the general case we prove the weaker inequality τ(G) ≤ ⌊(|G| - 1)/3⌋ + 1.

Original languageEnglish
Pages (from-to)273-286
Number of pages14
JournalPeriodica Mathematica Hungarica
Volume19
Issue number4
DOIs
StatePublished - Dec 1988

Keywords

  • AMS (MOS) subject classifications (1980): Primary 05C70, Secondary 05C05
  • bipartite graph
  • Edge decomposition
  • girth
  • n-dimensional cube
  • tree

ASJC Scopus subject areas

  • Mathematics (all)

Fingerprint

Dive into the research topics of 'The tree number of a graph with a given girth'. Together they form a unique fingerprint.

Cite this