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

Trudy Instituta matematiki, Tome 18 (2010) no. 2, pp. 79-86

Résumé

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)|$.