Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 09.02.2017 at 12:20 in S1, there is the following noon lecture:

Generalizations of theorems of Nash-Williams and Hakimi on graph decompositions

Daqing Yang

Abstract

The fractional arboricity of a graph G, denoted by gamma_1(G), is defined as gamma_1(G) =max_{H subgraph of G, v(H)>1} e(H)/(v(H)-1). The celebrated Nash-Williams' Theorem states that a graph G can be decomposed into at most k forests if and only if gamma_1(G)<=k.

In this talk, we begin with the trying for some more generalized form of Nash-Williams' Theorem. To do this, we have generalized the fractional arboricity gamma_1(G) to the fractional i-arboricity gamma_i(G); and generalized the concepts of forests and trees to i-forest and i-trees. Then we prove that a graph G can be decomposed into k i-forests if and only if gamma_i(G)<=k.

Suppose P is a partition of V(G), for i>=1, let phi_i(G)=min_{|P|>i} (e(G/P)/(|P|-i). The also well-known Tutte's Theorem states that a graph G has k edge-disjoint spanning trees if and only if phi_1(G)>=k. We also prove that a graph G has k edge-disjoint i-trees if and only if phi_i(G)>=k. This generalizes Tutte's Theorem.

By beginning with Hakimi's Theorem on decomposing a graph into peudoforests, some similar generalizations along this line have also been tried.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010