Skip to main content
added 139 characters in body
Source Link
John Machacek
  • 7.9k
  • 1
  • 23
  • 40

The paper

Harant, Jochen; Rautenbach, Dieter; Recht, Peter; Regen, Friedrich. Packing edge-disjoint cycles in graphs and the cyclomatic number. Discrete Math. 310 (2010), no. 9, 1456--1462

constructs graphs for which the difference between $d$ and the nmaximum number of edge-disjoint cycles is $k$ for any $k \in \mathbb{N}$. IfIf I understand the question correctly this shows you can't have a bound desired without some restrictions on the graphs (I have not thought more about the graphs described in the comments).

Edit: I understand the question correctly this shows you can't haveposted in a bound desired without some restrictions on the graphs (I haverush. This paper and it's references are relevant, but does not thought more about the graphs described inanswer the question. See comments) below.

The paper

Harant, Jochen; Rautenbach, Dieter; Recht, Peter; Regen, Friedrich. Packing edge-disjoint cycles in graphs and the cyclomatic number. Discrete Math. 310 (2010), no. 9, 1456--1462

constructs graphs for which the difference between $d$ and the nmaximum number of edge-disjoint cycles is $k$ for any $k \in \mathbb{N}$. If I understand the question correctly this shows you can't have a bound desired without some restrictions on the graphs (I have not thought more about the graphs described in the comments).

The paper

Harant, Jochen; Rautenbach, Dieter; Recht, Peter; Regen, Friedrich. Packing edge-disjoint cycles in graphs and the cyclomatic number. Discrete Math. 310 (2010), no. 9, 1456--1462

constructs graphs for which the difference between $d$ and the nmaximum number of edge-disjoint cycles is $k$ for any $k \in \mathbb{N}$. If I understand the question correctly this shows you can't have a bound desired without some restrictions on the graphs (I have not thought more about the graphs described in the comments).

Edit: I posted in a rush. This paper and it's references are relevant, but does not answer the question. See comments below.

Source Link
John Machacek
  • 7.9k
  • 1
  • 23
  • 40

The paper

Harant, Jochen; Rautenbach, Dieter; Recht, Peter; Regen, Friedrich. Packing edge-disjoint cycles in graphs and the cyclomatic number. Discrete Math. 310 (2010), no. 9, 1456--1462

constructs graphs for which the difference between $d$ and the nmaximum number of edge-disjoint cycles is $k$ for any $k \in \mathbb{N}$. If I understand the question correctly this shows you can't have a bound desired without some restrictions on the graphs (I have not thought more about the graphs described in the comments).