|
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)|$.
Received: 30.05.2010
Citation:
V. V. Lepin, S. A. Tsikhan, “The profile of the corona $G\wedge H$, where $G$ is a Halin graph, whose tree is a caterpillar”, Tr. Inst. Mat., 18:2 (2010), 79–86
Linking options:
https://www.mathnet.ru/eng/timb19 https://www.mathnet.ru/eng/timb/v18/i2/p79
|
|