Local properties and upper embeddability of connected multigraphs

From MaRDI portal





This paper unifies three known sufficient conditions for a connected multigraph \(G\) to be upper embeddable: (1) \(G\) is a 2-connected multigraph, and each edge of \(G\) belongs to a cycle of length 2 or 3; see \textit{Glakhov} [Preprint 80.8, IM AN USSR, Kiev, 24-27 (1980)]; (2) \(G\) is a connected, locally quasiconnected graph; see the author [Czech. Math. J. 35(110), 162-166 (1985; Zbl 0584.05031)]; (3) \(G\) is a connected, \(N_ 2\)-locally connected graph; see the author [Czech. Math. J. 41(116), No. 4, 731-735 (1991; Zbl 0760.05030)]. Let \(u\) be a vertex in multigraph \(G\); let \(E(u,G)\) denote the set of all edges in \(G\) not incident with \(u\), but incident with a vertex adjacent to \(u\). If \(E(u,G)\neq\varnothing\), let \(N_ 2(u,G)\) denote the submultigraph of \(G\) induced by \(E(u,G)\). Then \(G\) is said to be interlaced if: (i) if no cycle of length 2 or 3 passes through an edge incident with both \(u\) and \(v\), then \(N_ 2(u,G)\) and \(N_ 2(v,G)\) are both connected, for each pair of adjacent vertices \(u\) and \(v\) of \(G\); and (ii) \(N(w,G)\) is connected, for each vertex \(w\) adjacent to a cut-vertex of \(G\). (\(N(w,G)\) is the submultigraph of \(G\) induced by the neighbors of \(u\), if that neighborhood is nonempty.) Then the common generalization of the three theorems arising from (1), (2), (3) above is: Let \(G\) be a connected multigraph, with \(W\) a nonempty subset of \(V(G)\) such that the submultigraph of \(G\) induced by \(W\) is connected and interlaced, and either \(W= V(G)\) or \(G-W\) is a forest. Then \(G\) is upper embeddable.











This page was built for publication: Local properties and upper embeddability of connected multigraphs

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