Excluded conformal minors of Birkhoff-von Neumann graphs with equal global forcing number and maximum anti-forcing number
Abstract
Global forcing number and maximum anti-forcing number of matchable graphs (graphs with a perfect matching) were proposed in completely different situations with applications in theoretical chemistry.
Surprisingly for bipartite graphs and some nonbipartite graphs as solid bricks (or Birkhoff-von Neumann graphs) G, the global forcing number gf(G) is at least the maximum anti-forcing number Af(G).
It is natural to consider when gf(G) = Af(G) holds.
For convenience, we call a matchable graph G strongly uniform if each conformal matchable subgraph G' always satisfies gf(G') = Af(G').
In this article, by applying the ear decomposition theorem and discussing the existence of a Hamilton cycle with positions of chords, we give "excluded conformal minors" and "structural" characterizations of matchable bipartite graphs and Birkhoff-von Neumann graphs that are strongly uniform respectively.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요