RUS  ENG
Full version
JOURNALS // Proceedings of the Institute of Mathematics of the NAS of Belarus // Archive

Tr. Inst. Mat., 2010 Volume 18, Number 2, Pages 79–86 (Mi timb19)

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



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024