Geodesic
The profile of the corona $G\wedge H$, where $G$ is a Halin graph, whose tree is a caterpillar
Trudy Instituta matematiki, Tome 18 (2010) no. 2, pp. 79-86.

Voir la notice de l'article provenant de la source Math-Net.Ru

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)|$. 
@article{TIMB_2010_18_2_a6,
     author = {V. V. Lepin and S. A. Tsikhan},
     title = {The profile of the corona $G\wedge H$, where $G$ is a {Halin} graph, whose tree is a caterpillar},
     journal = {Trudy Instituta matematiki},
     pages = {79--86},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a6/}
}
TY  - JOUR
AU  - V. V. Lepin
AU  - S. A. Tsikhan
TI  - The profile of the corona $G\wedge H$, where $G$ is a Halin graph, whose tree is a caterpillar
JO  - Trudy Instituta matematiki
PY  - 2010
SP  - 79
EP  - 86
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a6/
LA  - ru
ID  - TIMB_2010_18_2_a6
ER  - 
%0 Journal Article
%A V. V. Lepin
%A S. A. Tsikhan
%T The profile of the corona $G\wedge H$, where $G$ is a Halin graph, whose tree is a caterpillar
%J Trudy Instituta matematiki
%D 2010
%P 79-86
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a6/
%G ru
%F TIMB_2010_18_2_a6
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. Trudy Instituta matematiki, Tome 18 (2010) no. 2, pp. 79-86. http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a6/

[1] Dzhordzh A., Lyu Dzh., Chislennoe reshenie bolshikh razrezhennykh sistem uravnenii, Mir, M., 1984 | MR

[2] Pissanetski S., Tekhnologiya razrezhennykh matrits, Mir, M., 1988 | MR

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[4] Lepin V.V., Zadacha o profile matrits i grafov, Preprint No 33(269), In-t matematiki AN BSSR, Minsk, 1986

[5] Kuo D., Chang G.J., “The profile minimization problem in trees”, SIAM J. Comput., 23:1 (1994), 71–81 | DOI | MR | Zbl

[6] Lepin V.V., “Zadacha o profile dereva i optimalnaya indeksatsiya reber”, Dokl. NAN Belarusi, 44:1 (2000), 22–28 | MR

[7] Lepin V.V., “Algoritm minimizatsii profilya grafa”, Vestsi NAN Belarusi. Ser. fiz.-mat. navuk, 2002, no. 3, 103–109 | MR

[8] Smyth W.F., “Algorithms for the reduction of matrix bandwidth and profile”, J. Comput. Appl. Math., 12-13 (1985), 551–561 | DOI | MR | Zbl

[9] Wiegers M., Monien B., “Bandwidth and profile minimization”, Lecture Notes in Comput. Sci., 344, 1988, 378–392 | MR

[10] Sloan S.W., “An algorithm for profile and wavefront reduction of sparse matrices”, Int. J. Numer. Meth. Eng., 23:2 (1986), 239–251 | DOI | MR | Zbl

[11] Snay R.A., “Reducing the profile of sparse symmetric matrices”, Bul. Geodesiques, 50 (1976), 341–352 | DOI | MR

[12] Diaz J., Petit J., Serna M., “A Survey of graph layout problems”, ACM Comput. Surveys, 34:3 (2002), 313–356 | DOI

[13] Lai Y.L., Williams K.L., “A survey of solved problems and applications on bandwidth, edgesum and profile of graphs”, Journal of Graph Theory, 31:22 (1999), 75–94 | 3.0.CO;2-S class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[14] Lai Y.L., Chang G.J., “On the profile of the corona of two graphs”, Information Processing Letters, 89 (2004), 287–292 | DOI | MR | Zbl

[15] Lin Y., Yuan J., “Minimum profile of grid networks”, Systems Sci. Math. Sci., 7:1 (1994), 56–66 | MR | Zbl

[16] Lin Y., Yuan J., “Profile minimization problem for matrices and graphs”, Acta Mathematicae Applicatae Sinica, English-Series, Yingyong Shuxue-Xuebas, 10:1 (1994), 107–112 | DOI | MR | Zbl

[17] Mai J., “Profiles of some condensable graphs”, J. System Sci. Math. Sci., 16 (1996), 141–148 | MR | Zbl

[18] Billionnet A., “On interval graphs and matrix profiles”, RAIRO Operations Research, 20 (1986), 245–256 | MR | Zbl

[19] Frucht R., Harary F., “On the coronas of two graphs”, Aequationes Math., 4 (1970), 322–324 | DOI | MR

[20] Chinn P.Z., Lin Y., Yuan J., “The bandwidth of the corona of two graphs”, Congr. Numer., 91 (1992), 141–152 | MR | Zbl

[21] Fink J.F., Jacobson M.S., Kinch L.F., Roberts J., “On graphs having domination number half their order”, Period. Math. Hungar., 16 (1985), 287–293 | DOI | MR | Zbl