On the Vertex Separation of Maximal Outerplanar Graphs

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.

Sequences of Maximal Degree Vertices in Graphs

2000 Mathematics Subject Classification: 05C35.

On strongly regular graphs with m2 = qm3 and m3 = qm2

2010 Mathematics Subject Classification: 05C50.