Displaying similar documents to “The absence of efficient dual pairs of spanning trees in planar graphs.”

On the Vertex Separation of Maximal Outerplanar Graphs

Markov, Minko (2008)

Serdica Journal of Computing

Similarity:

We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.

Edge shift distance between trees

Bohdan Zelinka (1992)

Archivum Mathematicum

Similarity:

Edge shift distance between isomorphism classes of graphs, introduced by M. Johnson, is investigated in the case of trees and compared with other distances.