Cozonal labelings of plane graphs
Let \(G\) be a plane graph with vertex set \(V(G)\), edge set \(E(G)\), and region set \(F(G)\) with multiple edges and loops allowed. A zonal labeling of \(G\) is a labeling \(\ell: V(G)\to\{1,2\}\subset \mathbb{Z}_3\) such that for every region \(R\in F(G)\) the sum of labels of all vertices on its boundary \(B_R\) is equal to zero, that is, \(\sum_{v\in B_R}\ell(v)=0\).\N\NLet \(X_v\) be the set of all regions with a vertex \(v\) on their boundary. A cozonal labeling of \(G\) is a labeling \(\ell^\ast: F(G)\to\{1,2\}\subset \mathbb{Z}_3\) such that the sum of labels of all regions \(R\in X_v\) (denoted by \(\ell^\ast(v)\)) is equal to zero, that is, \(\sum_{R\in X_v}\ell^\ast(R)=\ell^\ast(v)=0\).\N\NA graph possessing a zonal or cozonal labeling is called a zonal or cozonal graph, respectively. It is shown that a connected plane graph \(G\) is zonal if and only if it is cozonal. The number of regions having a vertex \(v\) on their boundary is denoted by \(\deg^\ast(v)\) and it is shown that if \(G\) is connected, then \(\deg^\ast(v)\leq\deg(v)\) and \(v\) is a cut-vertex if and only if \(\deg^\ast(v)<\deg(v)\).\N\NIt is further shown that if \(e\) is a bridge of \(G\), then \(G\) is cozonal if and only if both components of \(G-e\) are cozonal. It is also proved that the following classes of plane graphs are cozonal: plane triangulations, wheels \(W_n\) for \(n\equiv0\pmod3\), and 2-connected Eulerian graphs. A graph \(G\) with \(\Delta(G)=2\) is cozonal if and only if \(G\cong C_n, n\geq1\).\N\NLet \(B\) be the set of all bridges of \(G\). Then a connected cubic plane graph \(G\) is cozonal if and only if \(B=\emptyset\), and a connected plane graph \(G\) with \(\Delta(G)=3\) is cozonal if and only if \(G-B\) is \(k\)-regular for \(k\in\{2,3\}\).
This page was built for publication: Cozonal labelings of plane graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6914399)
