BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We derive a quadratic-time algorithm for the genus distribution of any 3-regular, biconnected series-parallel graph, which we extend to any biconnected series-parallel graph of maximum degree at most 3. Since the biconnected components of every graph of treewidth 2 are series-parallel graphs, this yields, by use of bar-amalgamation, a quadratic-time algorithm for every graph of treewidth at most 2 and maximum degree at most 3.
A graph G is equimatchable if any matching in G is a subset of a maximum-size matching. It is known that any 2-connected equimatchable graph is either bipartite or factor-critical. We prove that for any vertex v of a 2-connected factor-critical equimatchable graph G and a minimal matching M that isolates v the graph G∖(M∪{v}) is either K2n or Kn,n for some n. We use this result to improve the upper bounds on the maximum size of 2-connected equimatchable factor-critical graphs embeddable in the orientable surface of genus g to 4g+17 if g≤2 and to 12g+5 if g≥3. Moreover, for any nonnegative integer g we construct a 2-connected equimatchable factor-critical graph with genus g and more than 42g vertices, which establishes that the maximum size of such graphs is Θ(g). Similar bounds are obtained also for nonorientable surfaces. Finally, for any nonnegative integers g, h and k we provide a construction of arbitrarily large 2-connected equimatchable bipartite graphs with orientable genus g, respectively nonorientable genus h, and a genus embedding with face-width k.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.