Excluded conformal minors of Birkhoff-von Neumann graphs with equal global forcing number and maximum anti-forcing number
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915154345590784 |
|---|---|
| author | Zhang, Yaxian Wu, Yan Zhang, Heping |
| author_facet | Zhang, Yaxian Wu, Yan Zhang, Heping |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11391 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Excluded conformal minors of Birkhoff-von Neumann graphs with equal global forcing number and maximum anti-forcing number Zhang, Yaxian Wu, Yan Zhang, Heping Combinatorics 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. |
| title | Excluded conformal minors of Birkhoff-von Neumann graphs with equal global forcing number and maximum anti-forcing number |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.11391 |