Computing the genus of the 2-amalgamations of graphs

Let \(G_ 1\) and \(G_ 2\) be two subgraphs of a graph G such that \(G=G_ 1\cup G_ 2\) and \(G_ 1\cap G_ 2=\{x,y\}\), two distinct vertices; then G is said to be the 2-amalgamation of \(G_ 1\) and \(G_ 2\). The present authors [J. Graph Theory 5, 95-102 (1981; Zbl 0415.05022)] and \textit{S. Stahl} [Trans. Am. Math. Soc. 259, 129-145 (1980; Zbl 0441.05024)] have shown that if G is the 2-amalgamation of \(G_ 1\) and \(G_ 2\), then its orientable genus is given by \(\gamma (G)=\gamma (G_ 1)+\gamma (G_ 2)+\xi,\) where \(\xi\in \{-1,0,1\}\). In this paper a means is given for computing \(\xi\) exactly. Specifically, \(\xi =\lceil (3-\mu (G_ 1)\mu (G_ 2))/4\rceil,\) where \(\mu\) (G) is defined as follows. Let \(G^ 1=G\cup K_ 2\) with \(G\cap K_ 2=\{x,y\};\) let \(G^{11}=G\cup K_ 5\) with \(G\cap K_ 5=\{x,y\}\), where x and y are also two vertices on the interiors of nonadjacent edges of \(K_ 5\). Then \(\mu (G)=0,1,2\), or 3 according as \(\gamma (G)=\gamma (G^ 1)-1=\gamma (G^{11})-2,\) \(\gamma (G)=\gamma (G^ 1)-1=\gamma (G^{11})-1,\) \(\gamma (G)=\gamma (G^ 1)=\gamma (G^{11})-1,\) or \(\gamma (G)=\gamma (G^ 1)=\gamma (G^{11})\) respectively. In addition, the authors use this result to construct two irreducible graphs for each orientable surface.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Computing the genus of the 2-amalgamations of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1076031)