The tree number of a graph with a given girth |
| |
Authors: | M. Truszczyński |
| |
Affiliation: | (1) Department of Computer Science, University of Kentucky, 40506 Lexington, KY, USA |
| |
Abstract: | A family of subtrees of a graphG whose edge sets form a partition of the edge set ofG is called atree decomposition ofG. The minimum number of trees in a tree decomposition ofG is called thetree number ofG and is denoted by(G). It is known that ifG is connected then(G) |G|/2. In this paper we show that ifG is connected and has girthg 5 then(G) |G|/g + 1. Surprisingly, the case wheng = 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 andn-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. |
| |
Keywords: | Primary 05C70 Secondary 05C05 |
本文献已被 SpringerLink 等数据库收录! |
|