Characterizing path-like trees from linear configurations

Authors S. C. López, F. A. Muntaner-Batle

Publication date 24 May 2017

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: Assume that we embed the path

P_{n}

as a subgraph of a

2

-dimensional grid, namely,

P_{k} i m e s P_{l}

. Given such an embedding, we consider the ordered set of subpaths

L_{1}, L_{2}, l d o t s, L_{m}

which are maximal straight segments in the embedding, and such that the end of

L_{i}

is the beginning of

L_{i + 1}

. Suppose that

L_{i} c o n g P_{2}

, for some

i

and that some vertex

u

of

L_{i - 1}

is at distance

1

in the grid to a vertex

v

of

L_{i + 1}

. An elementary transformation of the path consists in replacing the edge of

L_{i}

by a new edge

u v

. A tree

T

of order

n

is said to be a path-like tree, when it can be obtained from some embedding of

P_{n}

in the

2

-dimensional grid, by a sequence of elementary transformations. Thus, the maximum degree of a path-like tree is at most

4

. Intuitively speaking, a tree admits a linear configuration if it can be described by a sequence of paths in such a way that only vertices from two consecutive paths, which are at the same distance of the end vertices are adjacent. In this paper, we characterize path-like trees of maximum degree

3

, with an even number of vertices of degree

3

, from linear configurations.

This page was built for publication: Characterizing path-like trees from linear configurations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6287072)