IJPAM: Volume 40, No. 3 (2007)

ON $k$-TREES WITH GIVEN LEAFAGES

Kensuke Hatanaka$^1$, Morimasa Tsuchiya$^2$
$^{1,2}$Department of Mathematical Sciences
Tokai University
Hiratsuka, Kanagawa, 259-1292, JAPAN
$^2$e-mail: [email protected]


Abstract.The leafage $l(G)$ of a chordal graph $G$ is the minimum number of leaves of a tree whose subtrees compose an intersection representation of $G.$ In [#!mckee!#] I.-J Lin, T.A.McKee and D.West give upper and lower bounds of $l(G)$ and algorithms for computing the leafages of non-clique $k$-trees. We show that for an integer $t,$ there exists a $k$-tree whose leafage is $t.$ And we consider some properties on $k$-trees.

Received: September 3, 2007

AMS Subject Classification: 05C05

Key Words and Phrases: $k$-tree, leafage

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 40
Issue: 3