The maximum forcing numbers of quadriculated tori
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910734768668672 |
|---|---|
| author | Liu, Qianqian Zhang, Yaxian Zhang, Heping |
| author_facet | Liu, Qianqian Zhang, Yaxian Zhang, Heping |
| contents | Klein and Randic (1985) proposed the concept of forcing number, which has an application in chemical resonance theory. Let $G$ be a graph with a perfect matching $M$. The forcing number of $M$ is the smallest cardinality of a subset of $M$ that is contained only in one perfect matching $M$. The maximum forcing number of $G$ is the maximum value of forcing numbers over all perfect matchings of $G$. Kleinerman (2006) obtained that the maximum forcing number of $2n\times 2m$ quadriculated torus is $nm$. By improving Kleinerman's approach, we obtain the maximum forcing numbers of all 4-regular quadriculated graphs on torus except one class. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_06331 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The maximum forcing numbers of quadriculated tori Liu, Qianqian Zhang, Yaxian Zhang, Heping Combinatorics Klein and Randic (1985) proposed the concept of forcing number, which has an application in chemical resonance theory. Let $G$ be a graph with a perfect matching $M$. The forcing number of $M$ is the smallest cardinality of a subset of $M$ that is contained only in one perfect matching $M$. The maximum forcing number of $G$ is the maximum value of forcing numbers over all perfect matchings of $G$. Kleinerman (2006) obtained that the maximum forcing number of $2n\times 2m$ quadriculated torus is $nm$. By improving Kleinerman's approach, we obtain the maximum forcing numbers of all 4-regular quadriculated graphs on torus except one class. |
| title | The maximum forcing numbers of quadriculated tori |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.06331 |