The minimum number of vertices and edges of connected graphs with ind-match$(G) = p$, min-match$(G) = q$ and match$(G) = r$
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909529810141184 |
|---|---|
| author | Matsuda, Kazunori Sato, Ryosuke Yoshida, Yuichi |
| author_facet | Matsuda, Kazunori Sato, Ryosuke Yoshida, Yuichi |
| contents | Let ind-match$(G)$, min-match$(G)$ and match$(G)$ denote the induced matching number, minimum matching number and matching number of a graph $G$, respectively. It is known that ind-match$(G) \leq $ min-match$(G) \leq {\rm match}(G) \leq$ 2min-match$(G)$ holds. In the present paper, we investigate the minimum number of vertices and edges of connencted simple graphs $G$ with ind-match$(G) = p$, min-match$(G) = q$ and ${\rm match}(G) = r$ for pair of integers $p, q, r$ such that $1 \leq p \leq q \leq r \leq 2q$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_01500 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The minimum number of vertices and edges of connected graphs with ind-match$(G) = p$, min-match$(G) = q$ and match$(G) = r$ Matsuda, Kazunori Sato, Ryosuke Yoshida, Yuichi Combinatorics 05C35, 05C69, 05C70 Let ind-match$(G)$, min-match$(G)$ and match$(G)$ denote the induced matching number, minimum matching number and matching number of a graph $G$, respectively. It is known that ind-match$(G) \leq $ min-match$(G) \leq {\rm match}(G) \leq$ 2min-match$(G)$ holds. In the present paper, we investigate the minimum number of vertices and edges of connencted simple graphs $G$ with ind-match$(G) = p$, min-match$(G) = q$ and ${\rm match}(G) = r$ for pair of integers $p, q, r$ such that $1 \leq p \leq q \leq r \leq 2q$. |
| title | The minimum number of vertices and edges of connected graphs with ind-match$(G) = p$, min-match$(G) = q$ and match$(G) = r$ |
| topic | Combinatorics 05C35, 05C69, 05C70 |
| url | https://arxiv.org/abs/2503.01500 |