| Autor: |
Jianhua Tu, Junyi Xiao, Rongling Lang |
| Jazyk: |
angličtina |
| Rok vydání: |
2023 |
| Předmět: |
|
| Zdroj: |
AIMS Mathematics, Vol 8, Iss 5, Pp 10021-10032 (2023) |
| Druh dokumentu: |
article |
| ISSN: |
2473-6988 |
| DOI: |
10.3934/math.2023507?viewType=HTML |
| Popis: |
Let $ G $ be a graph. A dissociation set of $ G $ is a subset of vertices that induces a subgraph with vertex degree at most 1. The dissociation polynomial of $ G $ is $ D_{G}(\lambda) = \sum_{D \in \mathcal{D}(G)} \lambda^{|D|} $, where $ \mathcal{D}(G) $ is the set of all dissociation sets of $ G $. In this paper, we prove that for any cubic graph $ G $ and any $ \lambda \in(0, 1] $, $ \frac{1}{|V(G)|} \ln D_{G}(\lambda) \leq \frac{1}{4} \ln D_{K_4}(\lambda) $ with equality if and only if $ G $ is a disjoint union of copies of the complete graph $ K_{4} $. When $ \lambda = 1 $, the value of $ D_G(\lambda) $ is exactly the number of dissociation sets of $ G $. Hence, for any cubic graph $ G $ on $ n $ vertices, $ |\mathcal{D}(G)|\leq|\mathcal{D}(K_4)|^{n/4} = 11^{n/4}. $ |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
