Nonorientable genus of nearly complete bipartite graphs
type: Item
instance of: scholarly article
title: Nonorientable genus of nearly complete bipartite graphs
zbMATH Open document ID: 0628.05026
DOI: 10.1007/BF02187903
author: Bojan Mohar
published in: Discrete \& Computational Geometry
publication date: 1988-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131042
review text: The graph obtained by deleting k independent edges from the complete bipartite graph \(K_{m,n}\) is denoted by G(m,n,k). Set \(f(m,n,k)=((m- 2)(n-2)-k)/2\). The lower bound \({\tilde \gamma}\)(G(m,n,k))\(\geq \lceil f(m,n,k)\rceil\) is readily obtained. Using surgical imbedding techniques, the author shows that the lower bound is attained - except in trivial cases where F(m,n,k)\(\leq 0\) and possibly in the extreme cases \(G(k+1,k,k)\) with k even and G(k,k,k) with \(k=5\) (the graph is planar) or not divisible by 4. Strict inequality may hold, as \({\tilde \gamma}\)(G(5,4,4))\(=2\) and \({\tilde \gamma}\)(G(5,5,5))\(=3\).
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 4021166
zbMATH Keywords: edge deletion
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Q3856672
cites work: Orientable and non orientable genus of the complete bipartite graph
cites work: Q3890714
cites work: Minimal ordered triangulations of surfaces
cites work: Q3712350
cites work: Der vollständige paare Graph auf nichtorientierbaren Flächen.
cites work: The embeddings of a graph—A survey
cites work: Q5684700
description: scientific article; zbMATH DE number 4021166