A CHARACTERIZATION OF k-TH POWERS P n,k OF PATHS IN TERMS OF k-TREES

Let G be a k-tree such that |{v ∈ V(G): deg G (v) = k}| = 2, n = |V(G)| ≥ 2k + 2, and the maximum degree of G is at most 2k. In this paper, we will show that such a k-tree G is isomorphic to P n,k . In this way, we give a new characterization of k-th power (i.e. P n,k ) of paths with n vertices in t...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2001-08, Vol.12 (4), p.435-443
Main Authors: Yamazaki, Koich, Tani, Sei'ichi, Nishino, Tetsuro
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a k-tree such that |{v ∈ V(G): deg G (v) = k}| = 2, n = |V(G)| ≥ 2k + 2, and the maximum degree of G is at most 2k. In this paper, we will show that such a k-tree G is isomorphic to P n,k . In this way, we give a new characterization of k-th power (i.e. P n,k ) of paths with n vertices in terms of k-trees.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054101000576