On extremal sizes of locally k-tree graphs

Mieczysław Borowiecki; Piotr Borowiecki; Elżbieta Sidorowicz; Zdzisław Skupień

doi:10.1007/s10587-010-0037-z

On extremal sizes of locally k-tree graphs

Abstrakt

A graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k>=0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k >= 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n-vertex locally k-tree graph is between $Omega(n)$ and $O(n^2)$, where both boundsare asymptotically tight. In contrast, the number of edges in an n-vertex k-tree is always linear in n.

Cytowania

5

CrossRef
0

Web of Science
6

Scopus

Autorzy (4)

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:: CZECHOSLOVAK MATHEMATICAL JOURNAL nr 60, strony 571 - 587,
ISSN: 0011-4642
Język:: angielski
Rok wydania:: 2010
Opis bibliograficzny:: Borowiecki M., Borowiecki P., Sidorowicz E., Skupień Z.: On extremal sizes of locally k-tree graphs// CZECHOSLOVAK MATHEMATICAL JOURNAL. -Vol. 60, nr. Iss. 2 (2010), s.571-587
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10587-010-0037-z
Weryfikacja:: Politechnika Gdańska