The profile of the corona $G\wedge H$, where $G$ is a Halin graph, whose tree is a caterpillar
V. V. Lepin,
S. A. Tsikhan Institute of Mathematics of the National Academy of Sciences of Belarus
Abstract:
Let
$G=(V,E)$ be a graph on
$n$ vertices. A 1-1 mapping
$f\colon V\to\{1,2,\dots,n\}$ is called a linear arrangement of
$G$. Given a graph
$G$, the profile problem is to find the profile of
$$
G:p(G)=\min_f\sum_{v\in V}\max_{u\in N[v]}(f(v)-f(u)),
$$
where
$N[v]=\{v\}\cup\{u\in V:\{v,u\}\in E\}$. A Halin graph
$H=T\cup C$ is obtained by embedding a tree
$T$ having no degree two nodes in the plane, and then adding a cycle
$C$ to join the leaves of
$T$ in such a way that the resulting graph is planar. The corona of graphs
$G_1$ and
$G_2$, on
$n_1$ and
$n_2$ vertices, respectively, is denoted by
$G_1\wedge G_2$ and contains one copy of
$G_1$ and
$n_1$ copies of
$G_2$. Each distinct vertex of
$G_1$ is joined to every vertex of the corresponding copy of
$G_2$. This paper shows that, if
$G$ is a Halin graph such that the tree
$T$ is a caterpillar then
$p(G)=3(n-2)$ and
$p(G\wedge H)=3(n-2)+np(H)+(3n-6)m$, where
$n=|V(G)|$,
$m=|V(H)|$.
UDC:
519.1 Received: 30.05.2010