Counting the number of dissociation sets in cubic graphs

Jianhua Tu; Junyi Xiao; Rongling Lang; Jianhua Tu; Junyi Xiao; Rongling Lang

doi:10.3934/math.2023507

AIMS Mathematics

2023, Volume 8, Issue 5: 10021-10032. doi: 10.3934/math.2023507

Previous Article Next Article

Research article

Counting the number of dissociation sets in cubic graphs

1.
School of Mathematics and Statistics, Beijing Technology and Business University, Beijing 100048, China
2.
Department of Mathematics, Beijing University of Chemical Technology, Beijing 100029, China
3.
School of Electronics and Information Engineering, Beihang University, Beijing 100191, China

Received: 28 September 2022 Revised: 09 February 2023 Accepted: 15 February 2023 Published: 23 February 2023
MSC : 05A17, 05C31, 05C69

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}.$

Keywords:

Citation: Jianhua Tu, Junyi Xiao, Rongling Lang. Counting the number of dissociation sets in cubic graphs[J]. AIMS Mathematics, 2023, 8(5): 10021-10032. doi: 10.3934/math.2023507

Related Papers:

[1]	Wenke Zhou, Guo Chen, Hongzhi Deng, Jianhua Tu . Enumeration of dissociation sets in grid graphs. AIMS Mathematics, 2024, 9(6): 14899-14912. doi: 10.3934/math.2024721
[2]	Jianhua Tu, Lei Zhang, Junfeng Du, Rongling Lang . Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree. AIMS Mathematics, 2022, 7(1): 569-578. doi: 10.3934/math.2022036
[3]	Muhammad Tanveer, Imran Ahmed, Ali Raza, Sumaira Nawaz, Yu-Pei Lv . New escape conditions with general complex polynomial for fractals via new fixed point iteration. AIMS Mathematics, 2021, 6(6): 5563-5580. doi: 10.3934/math.2021329
[4]	Jiangmin Pan, Yingnan Zhang . On cubic semisymmetric bi-Cayley graphs on nonabelian simple groups. AIMS Mathematics, 2022, 7(7): 12689-12701. doi: 10.3934/math.2022702
[5]	Ningge Huang, Lily Chen . AVD edge-colorings of cubic Halin graphs. AIMS Mathematics, 2023, 8(11): 27820-27839. doi: 10.3934/math.20231423
[6]	Kai An Sim, Kok Bin Wong . On the cooling number of the generalized Petersen graphs. AIMS Mathematics, 2024, 9(12): 36351-36370. doi: 10.3934/math.20241724
[7]	Ali N. A. Koam . Metric based resolvability of cycle related graphs. AIMS Mathematics, 2024, 9(4): 9911-9925. doi: 10.3934/math.2024485
[8]	Xiaoling Sun, Yubin Gao, Jianwei Du . On symmetric division deg index of unicyclic graphs and bicyclic graphs with given matching number. AIMS Mathematics, 2021, 6(8): 9020-9035. doi: 10.3934/math.2021523
[9]	Akbar Ali, Sneha Sekar, Selvaraj Balachandran, Suresh Elumalai, Abdulaziz M. Alanazi, Taher S. Hassan, Yilun Shang . Graphical edge-weight-function indices of trees. AIMS Mathematics, 2024, 9(11): 32552-32570. doi: 10.3934/math.20241559
[10]	M. E. Abdel-Aal, S. A. Bashammakh . A study on the varieties of equivalent cordial labeling graphs. AIMS Mathematics, 2024, 9(12): 34720-34733. doi: 10.3934/math.20241653

Abstract

$\frac{1}{|V(G)|} \ln D_{G}(\lambda) \leq \frac{1}{4} \ln D_{K_4}(\lambda)$

1. Introduction

All graphs considered in this paper are simple, undirected and labeled. Let $G$ be a graph. A subset of vertices of $G$ is called a dissociation set if it induces a subgraph with vertex degree at most 1. The empty set is also thought to be a dissociation set of $G$ . Let $\mathcal{D}(G)$ be the set of all dissociation sets of $G$ and $|\mathcal{D}(G)|$ be the total number of dissociation sets of $G$ . The dissociation polynomial of $G$ is $D_{G}(\lambda) = \sum_{D \in \mathcal{D}(G)} \lambda^{|D|}$ .

The concept of dissociation sets was introduced by Yannakakis ^[7] in 1981, and has been studied extensively in the last four decades. It is also a natural generalization of the well known independent set. Compared with the independent set, the study of dissociated set is more difficult; for example, the problem of finding a maximum dissociation set is NP-hard in bipartite graphs, while the problem of finding a maximum independent set is polynomially solvable in bipartite graphs.

The extremal problems of counting the number of a given graph substructure of a graph of a given type has got lots of attention in the last two decades ^[1,4,5,6,8]. In 2017, Davies et al. ^[2] introduced a novel technique called the occupancy method and used this method to prove tight upper bounds on the independence polynomial and matching polynomial of $d$ -regular graphs. The occupancy method has also been applied to other counting problems ^[2,3,6].

In this paper, we use the occupancy method to give a tight upper bound on the dissociation polynomial of cubic graphs, and answer the question of which cubic graphs have the largest number of dissociation sets.

We first introduce a probability distribution over all dissociation sets in $G$ , parameterized by a real number $\lambda > 0$ , where each dissociation set $D$ is chosen with probability,

$\Pr[D] = \frac{\lambda^{|D|}}{\sum\limits_{D \in \mathcal{D}(G)} \lambda^{|D|}} = \frac{\lambda^{|D|}}{D_G(\lambda)}.$

We call the probability distribution the dissociation probability model. The dissociation occupancy fraction of the dissociation probability model, denoted by $\beta_{G}(\lambda)$ , is the expected fraction of vertices of $G$ contained in a random dissociation set $D$ chosen from the dissociation probability model. Specifically,

$\begin{align} \beta_{G}(\lambda) & = \frac{1}{|V(G)|} \sum\limits_{v \in G} \Pr[v \in D] = \frac{1}{|V(G)|} \frac{\sum\limits_{D \in \mathcal{D}}|D| \lambda^{|D|}}{D_{G}(\lambda)}\\ & = \frac{1}{|V(G)|} \cdot\frac{\lambda\cdot (D_{G}(\lambda))^{\prime}}{D_{G}(\lambda)} = \lambda \cdot\left(\frac{1}{|V(G)|} \ln D_{G}(\lambda)\right)^{\prime}. \end{align}$

(1.1)

By (1.1) and the fact that $D_G(0) = 1$ , we have

$\begin{align} \frac{1}{|V(G)|} \ln D_{G}(\lambda) = \int_{0}^{\lambda} \frac{\beta_{G}(t)}{t} dt. \end{align}$

(1.2)

The main contribution of this work is to prove a tight upper bound on the dissociation occupancy fractions of cubic graphs for $\lambda\in(0, 1]$ .

Theorem 1.1. For any cubic graph $G$ and any $\lambda \in(0, 1]$ ,

$\beta_{G}(\lambda) \leq \beta_{K_{4}}(\lambda),$

with equality if and only if $G$ is a disjoint union of copies of the complete graph $K_{4}$ .

By (1.2), we can directly obtain the following corollary:

Corollary 1.1. 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}$ .

The value of $D_G(1)$ is exactly the total number of dissociation sets of $G$ . Note that $D_{G\cup H}(\lambda) = D_{G}(\lambda)\cdot D_{H}(\lambda)$ , where $G\cup H$ is a disjoint union of two graphs $G$ and $H$ . It follows from Corollary 1.1 that a disjoint union of $n/4$ copies of the complete graph $K_4$ has the most dissociation sets of all cubic graphs on $n$ vertices. Hence, for any cubic graph $G$ on $n$ vertices,

$|\mathcal{D}(G)|\leq |\mathcal{D}(K_4)|^{n/4} = 11^{n/4}.$

2. Proof of Theorem 1.1

The dissociation polynomial of the complete graph $K_4$ is

$D_{K_4}(\lambda) = 1 + 4 \lambda + 6 \lambda^2,$

and its dissociation occupancy fraction is

$\beta_{K_4}(\lambda) = \frac{1}{4} \cdot \frac{\lambda\ (D_{K_4}(\lambda))^{\prime}}{D_{K_4}(\lambda)} = \frac{\lambda+3 \lambda^2}{ 1 + 4 \lambda + 6 \lambda^2}.$

Let $G$ be a cubic graph. We choose a vertex, $v$ , uniformly from $V(G)$ at random, and a dissociation set $D$ from the dissociation probability model. We say that the vertex, $v$ , is occupied if $v\in D$ , and is otherwise unoccupied. The $i$ -th neighborhood of $v$ , denoted by $N_i(v)$ , is the set of vertices of $G$ each of which is at distance $i$ from $v$ . Clearly, $N_1(v) = N(v)$ .

We divide the neighborhood $N(v)$ of $v$ into three vertex sets, $A_{0}$ , $A_{1}$ , and $A_{2}$ , as shown in , where the black vertices represent the vertices belonging to the dissociation set $D$ . A vertex $u\in N(v)$ is called externally uncovered if none of the vertices in $N(u)\cap N_2(v)$ are in $D$ . The set $A_2$ consists of vertices of $N(v)$ that are externally uncovered. A vertex $u\in N(v)\setminus A_2$ is called partly externally covered if only one vertex in $(N(u)\cap N_2(v))\cup (N_2(u)\cap N_3(v))$ is in $D$ , and the set $A_1$ consists of vertices in $N(v)\setminus A_2$ that are partly externally covered. Let $A_0: = N(v)\setminus (A_1\cup A_2)$ , where every vertex of $A_0$ is called an externally covered vertex. Let $A'_1 = (\cup_{u\in A_1}N(u)) \cap N_2(v)\cap D$ .

Figure 1. Divide the neighborhood

$N(v)$ of

$v$ into three vertex sets

$A_{0}$ ,

$A_{1}$ , and

$A_{2}$ .

DownLoad: Full-Size Img PowerPoint

It is worth pointing out that, although we have sampled a dissociation set $D$ of $G$ , it is best to think of the information about which vertices in $N(v)\cup\{v\}$ belong to $D$ as having not been revealed.

Then, we define a local view of the subgraph induced by $\{v\} \cup A_{1} \cup A_{2} \cup A_{1}^{\prime}$ and record the implementation of the local view as a configuration $C$ , while denoting the dissociation polynomial of $C$ by $D_{C}(\lambda)$ . Let $H$ be the subgraph induced by $A_{1} \cup A_{2}$ and define $D_{H}(\lambda)$ as the dissociation polynomial of $H$ for the given configuration $C$ . Let $a_{i}\ (i = 0, 1, 2)$ be the size of the set $A_{i}\ (i = 0, 1, 2)$ , and $a'_1$ be the size of the set $A'_1$ . Clearly, ${a_{1}}^{\prime} \leq a_{1}$ , $a_{1}+a_{2} \leq 3$ . We write $C = C_{i}({a_{1}}^{\prime}, a_{1}, a_{2})$ for a local view of $v$ with respect to $D$ .

It is easy to check that, for cubic graphs, there is a total of 34 configurations up to symmetries, which are pictured in Figure 2.

Figure 2. All possible configurations that can arise from a cubic graph.

DownLoad: Full-Size Img PowerPoint

Let $\mathcal{C}$ be the set of all possible configurations $C$ . Note that $C_4(0, 0, 3)$ is the only configuration that can arise from the complete graph $K_4$ .

For every configuration $C$ , let $p(C)$ denote the probability that the configuration occurs, and $\beta_{C}(\lambda)$ be the conditional probability that $v$ is occupied in given configuration $C$ . The dissociation occupancy fraction of $G$ can be written as:

$\begin{align*} \beta_{G}(\lambda) & = \frac{1}{|V(G)|} \sum\limits_{v \in G} \Pr[v \in D]\\ & = \sum\limits_{C \in \mathcal{C}}\operatorname{Pr}[v \in D \mid C]\cdot p(C)\\ & = \sum\limits_{C \in \mathcal{C}} \beta_{C}(\lambda) \cdot p(C). \end{align*}$

We select a vertex $u$ uniformly from the neighbors of $v$ at random, and consider the following conditional probabilities:

$\begin{aligned} \beta_{t}^{v}(C) & = \Pr[v\in D \text { and } d_{G[D]}(v) = t \mid C] \quad\text{and}\\ \beta_{t}^{u}(C) & = \Pr[u\in D \text { and } d_{G[D]}(u) = t \mid C], \\ \end{aligned}$

where $t\in\{0, 1\}$ .

The expressions for $\beta_{C}(\lambda)$ , $\beta_{0}^{v}(C)$ , $\beta_{1}^{v}(C)$ , $\beta_{0}^{u}(C)$ and $\beta_{1}^{u}(C)$ and all configurations $C\in \mathcal{C}$ are evaluated and listed in Appendix A.

By consistency conditions, we use the fact that, for any $t\in\{0, 1\}$ , the probability that $v$ is in $D$ and has degree $t$ in the induced subgraph $G[D]$ equals the probability that a random neighbor $u$ of $v$ is in $D$ and has degree $t$ in $G[D]$ , that is,

$\sum\limits_{C \in \mathcal{C}} \beta_{t}^{v}(C) \cdot p(C) = \sum\limits_{C \in \mathcal{C}} \beta_{t}^{u}(C) \cdot p(C), \text { for } t = 0, 1.$

Hence, we have two constraints on the probability distribution on configurations.

Now, we write the following linear programming with decision variables $p(C)$ and three constraints:

$\begin{aligned} (LP) \qquad\beta_{\max }(\lambda) = \max\ \ & \sum\limits_{C \in \mathcal{C}} \beta_{C}(\lambda) p(C) \\ s. t. \quad & \sum\limits_{C \in \mathcal{C}} p(C) = 1 \\ & \sum\limits_{C \in \mathcal{C}} p(C) \cdot ( \beta_{t}^{v}(C)- \beta_{t}^{u}(C)) = 0 \quad\text { for } t = 0, 1\\ & p(C) \geq 0 \quad\forall C \in \mathcal{C}. \end{aligned}$

The dual linear programming of LP is as follows:

$\begin{aligned} (DP)\qquad\beta_{\max }(\lambda) = \min\ \ &\Lambda_{p} \\ s. t. \quad&\Lambda_{p}+\sum\limits_{t = 0}^{1} \Lambda_{t}[\beta_{t}^{v}(C)-\beta_{t}^{u}(C)] \geq \beta_{C}(\lambda) \quad \forall C \in \mathcal{C}, \end{aligned}$

where $\Lambda_{p}, \Lambda_{0}, \Lambda_{1}$ are the decision variables of DP.

Our goal is to show that, when $\lambda\in (0, 1]$ , the optimal value of LP is $\beta_{\max }(\lambda) = \beta_{K_{4}}(\lambda)$ . The solution that $p(C_{4}(0, 0, 3)) = 1$ and $p(C) = 0$ for all other configurations is clearly feasible to LP. It suffices to find a feasible solution to DP with $\Lambda^*_p = \beta_{K_{4}}(\lambda)$ for $\lambda\in(0, 1]$ . Define the slack function of every configuration $C$ as:

$S_{C}(\lambda, \Lambda_{0}, \Lambda_{1}) = \beta_{K_{4}}(\lambda)-\beta_{C}(\lambda)+\sum\limits_{t = 0}^{1} \Lambda_{t}[\beta_{t}^{v}(C)-\beta_{t}^{u}(C)].$

Claim 2.1. Let

$\begin{aligned} \Lambda_{0}^{*}(\lambda) = &\frac{3\lambda^{2}}{1+4\lambda+6\lambda^{2}}, \\ \Lambda_{1}^{*}(\lambda) = &\frac{3\lambda+9\lambda^{2}}{2+8\lambda+12\lambda^{2}}. \end{aligned}$

Then, for every configuration $C\in\mathcal{C}$ and any $\lambda \in (0, 1]$ ,

$S_{C}(\lambda, \Lambda_{0}^{*}(\lambda), \Lambda_{1}^{*}(\lambda))\geq 0.$

Proof. Proof of Claim 2.1. The values of $S_{C}(\lambda, \Lambda_{0}^{*}(\lambda), \Lambda_{1}^{*}(\lambda))$ for all configurations $C\in\mathcal{C}$ are calculated and listed in . Let $\mathcal{C}_1: = \{C_4, C_{25}, C_{32}, C_{34}\}$ and $\mathcal{C}_2: = \{C_2, C_5, C_8, C_{13}, C_{22}\}$ .

Table 1. The values of

$S_{C}(\lambda, \Lambda_{0}^{*}(\lambda), \Lambda_{1}^{*}(\lambda))$ for all configurations

$C \in \mathcal{C}$ .

	$S_{C}(\lambda, \Lambda_{0}^{}, \Lambda_{1}^{})$	$\lambda(t) =\frac{t}{1+t}$
$C_{1}(0, 0, 3)$	$\frac {3\lambda^{3}+4\lambda^{4}}{1+8\lambda+28\lambda^{2}+49\lambda^{3}+40\lambda^{4}+6\lambda^{5}}$
$C_{2}(0, 0, 3)$	$\frac{2\lambda^{3}+2\lambda^{4}-\lambda^{5}}{1+8\lambda+28\lambda^{2}+49\lambda^{3}+40\lambda^{4}+6\lambda^{5}}$	$\frac {2 t^{3}+6t^{4}+3t^{5}} {1+13t+70t^{2}+191t^{3}+259t^{4}+132t^{5}}$
$C_{3}(0, 0, 3)$	$\frac{\lambda^{3}+ \lambda^{4}}{1 +8\lambda+28\lambda^{2}+48\lambda^{3}+36\lambda^{4}}$
$C_{4}(0, 0, 3)$	0
$C_{5}(1, 1, 2)$	$\frac{\lambda^{2}+7\lambda^{3}+5\lambda^{4}-\lambda^{5}}{2+16\lambda+54\lambda^{2}+90\lambda^{3}+68\lambda^{4}+12\lambda^{5}}$	$\frac{t^{2}+10t^{3}+22t^{4}+12t^{5}}{2+26t+138t^{2}+368t^{3}+484t^{4}+242t^{5}}$
$C_{6}(1, 1, 2)$	$\frac{\lambda^{2}+6\lambda^{3}+3\lambda^{4}}{2+16\lambda+52\lambda^{2}+80\lambda^{3}+48\lambda^{4}}$
$C_{7}(1, 1, 2)$	$\frac{\lambda^{2}+4\lambda^{3}+\lambda^{4}}{2+16\lambda+52\lambda^{2}+80\lambda^{3}+48\lambda^{4}}$
$C_{8}(1, 1, 2)$	$\frac {\lambda^{2}+5\lambda^{3}+\lambda^{4}-3\lambda^{5}}{2+16\lambda+54\lambda^{2}+90\lambda^{3}+68\lambda^{4}+12\lambda^{5}}$	$\frac {t^{2}+8t^{3}+14t^{4}+4t^{5}}{2+26t+138t^{2}+368t^{3}+484t^{4}+242t^{5}}$
$C_{9}(1, 2, 1)$	$\frac {\lambda^{4}+4\lambda^{3}+\lambda^{2}}{1+8\lambda+25\lambda^{2}+36\lambda^{3}+18\lambda^{4}}$
$C_{10}(1, 2, 1)$	$\frac {\lambda^{4}+4\lambda^{3}+\lambda^{2}}{1+8\lambda+25\lambda^{2}+36\lambda^{3}+18\lambda^{4}}$
$C_{11}(1, 2, 1)$	$\frac {2\lambda^{2}+7\lambda^{3}+\lambda^{4}}{2+16\lambda+48\lambda^{2}+64\lambda^{3}+24\lambda^{4}}$
$C_{12}(1, 2, 1)$	$\frac {\lambda^{2}+3\lambda^{3}}{1+8\lambda+23\lambda^{2}+28\lambda^{3}+6\lambda^{4}}$
$C_{13}(2, 2, 1)$	$\frac{\lambda^{2}+4\lambda^{3}+\lambda^{4}-\lambda^{5}}{1+8\lambda+26\lambda^{2}+41\lambda^{3} +28\lambda^{4}+6\lambda^{5}}$	$\frac {t^{2}+7t^{3}+12t^{4}+5t^{5}}{1+13t+68t^{2}+177t^{3}+225t^{4}+110t^{5}}$
$C_{14}(2, 2, 1)$	$\frac{\lambda^{2}+4\lambda^{3}+\lambda^{4}}{1+8\lambda+25\lambda^{2}+36\lambda^{3}+18\lambda^{4}}$
$C_{15}(2, 2, 1)$	$\frac {2\lambda^{2}+7\lambda^{3}+\lambda^{4}}{2+16\lambda+50\lambda^{2}+72\lambda^{3}+36\lambda^{4}}$
$C_{16}(2, 2, 1)$	$\frac{\lambda^{2}+3\lambda^{3}}{1+8\lambda+24\lambda^{2}+32\lambda^{3}+12\lambda^{4}}$
$C_{17}(1, 3, 0)$	$\frac {3\lambda^{2}+9\lambda^{3}}{2+16\lambda+44\lambda^{2}+48\lambda^{3}}$
$C_{18}(1, 3, 0)$	$\frac {3\lambda^{2}+9\lambda^{3}}{2+16\lambda+44\lambda^{2}+48\lambda^{3}}$
$C_{19}(2, 3, 0)$	$\frac{3\lambda^{2}+9\lambda^{3}}{2+16\lambda+48\lambda^{2}+64\lambda^{3}+24\lambda^{4}}$
$C_{20}(2, 3, 0)$	$\frac{3\lambda^{2}+9\lambda^{3}}{2+16\lambda+48\lambda^{2}+64\lambda^{3}+24\lambda^{4}}$
$C_{21}(2, 3, 0)$	$\frac {3\lambda^{2}+9\lambda^{3}}{2+16\lambda+46\lambda^{2}+56\lambda^{3}+12\lambda^{4}}$
$C_{22}(3, 3, 0)$	$\frac {3\lambda^{2}+9\lambda^{3}-\lambda^{4}-3\lambda^{5}}{2+16\lambda+50\lambda^{2}+74\lambda^{3}+44\lambda^{4}+12\lambda^{5}}$	$\frac {3t^{2}+18t^{3}+26t^{4}+8t^{5}}{2+26t+134t^{2}+340t^{3}+416t^{4}+198t^{5}}$
$C_{23}(3, 3, 0)$	$\frac{3\lambda^{2}+9\lambda^{3}}{2+16\lambda+48\lambda^{2}+64\lambda^{3}+24\lambda^{4}}$
$C_{24}(0, 0, 2)$	$\frac{\lambda^{3}+\lambda^{4}}{1+7\lambda+21\lambda^{2}+30\lambda^{3}+18\lambda^{4}}$
$C_{25}(0, 0, 2)$	0
$C_{26}(1, 1, 1)$	$\frac{\lambda^{2}+4\lambda^{3}+\lambda^{4}}{2+14\lambda+40\lambda^{2}+52\lambda^{3}+24\lambda^{4}}$
$C_{27}(1, 1, 1)$	$\frac{\lambda^{2}+3\lambda^{3}}{2+14\lambda+38\lambda^{2}+44\lambda^{3}+12\lambda^{4}}$
$C_{28}(1, 2, 0)$	$\frac{\lambda^{2}}{1+4\lambda+6\lambda^{2}}$
$C_{29}(1, 2, 0)$	$\frac{\lambda^{2}}{1+4\lambda+6\lambda^{2}}$
$C_{30}(2, 2, 0)$	$\frac{\lambda^{2}+3\lambda^{3}}{1+7\lambda+19\lambda^{2}+22\lambda^{3}+6\lambda^{4}}$
$C_{31}(2, 2, 0)$	$\frac{\lambda^{2}}{1+4\lambda+6\lambda^{2}}$
$C_{32}(0, 0, 1)$	0
$C_{33}(1, 1, 0)$	$\frac{\lambda^{2}+3\lambda^{3}}{2+12\lambda+28\lambda^{2}+24\lambda^{3}}$
$C_{34}(0, 0, 0)$	0

| Show Table

DownLoad: CSV

For every configuration $C\in\mathcal{C}_1$ , as can be seen from Table 1, we have

$S_{C}(\lambda, \Lambda_{0}^{*}(\lambda), \Lambda_{1}^{*}(\lambda)) = 0,$

for all $\lambda > 0$ .

For every configuration $C\in\mathcal{C}_2$ , we use an auxiliary function $\lambda(t) = \frac{t}{1+t}$ which maps $[0, +\infty)$ to $[0, 1)$ . Also shown in is that $S_{C}(\lambda(t), \Lambda_{0}^{*}(\lambda(t)), \Lambda_{1}^{*}(\lambda(t)))$ is the ratio of two polynomials in $t$ with positive coefficients. Thus,

$S_{C}(\lambda, \Lambda_{0}^{*}(\lambda), \Lambda_{1}^{*}(\lambda)) > 0$

for all $\lambda\in(0, 1)$ . It is easy to check that when $\lambda = 1$ , $S_{C}(\lambda, \Lambda_{0}^{*}(\lambda), \Lambda_{1}^{*}(\lambda)) > 0$ . Thus, we have

$S_{C}(\lambda, \Lambda_{0}^{*}(\lambda), \Lambda_{1}^{*}(\lambda)) > 0$

for all $\lambda\in(0, 1]$ .

For every configuration $C\in\mathcal{C}\setminus(\mathcal{C}_1\cup\mathcal{C}_2)$ , $S_{C}(\lambda, \Lambda_{0}^{*}(\lambda), \Lambda_{1}^{*}(\lambda))$ is the ratio of two polynomials in $\lambda$ with positive coefficients, it follows that

$S_{C}(\lambda, \Lambda_{0}^{*}(\lambda), \Lambda_{1}^{*}(\lambda)) > 0,$

for all $\lambda > 0$ .

Now, we have obtained a feasible solution to DP with $\Lambda^*_p = \beta_{K_{4}}(\lambda)$ for $\lambda \in(0, 1]$ and proved that $\beta_{G}(\lambda)\leq\beta_{K_{4}}(\lambda)$ for all cubic graphs $G$ and all $\lambda \in(0, 1]$ . Next, we will prove that unions of copies of the complete graph $K_4$ are the only graphs that maximize $\beta_G(\lambda)$ among all cubic graphs.

Claim 2.2. Let $G$ be a cubic graph with $\beta_{G}(\lambda) = \beta_{K_{4}}(\lambda)$ , only the configuration $C_{4}(0, 0, 3)$ appears with positive probability.

Proof. Proof of Claim 2.2 It can be seen from the proof of Claim 2.1 that for every configuration $C\in\mathcal{C}\setminus\mathcal{C}_1$ and any $\lambda\in(0, 1]$ ,

$S_{C}(\lambda, \Lambda_{0}^{*}(\lambda), \Lambda_{1}^{*}(\lambda)) > 0.$

It follows from complementary slackness that $p(C) = 0$ for every configuration $C\in\mathcal{C}\setminus\mathcal{C}_1$ . It suffices to prove that $p(C_{25}) = p(C_{32}) = p(C_{34}) = 0$ .

Suppose that the random dissociation set chosen is the empty dissociation set. If $p(C_{25}) > 0$ , then either $p(C_{2}) > 0$ or $p(C_{3}) > 0$ . If $p(C_{32}) > 0$ , then either $p(C_{1}) > 0$ , or $p(C_{2}) > 0$ , or $p(C_{3}) > 0$ . If $p(C_{34}) > 0$ , then either $p(C_{1}) > 0$ or $p(C_{2}) > 0$ . In each case, we have a contradiction.

Therefore, the configuration $C_{4}(0, 0, 3)$ is the unique maximizer of LP, which implies that unions of copies of the complete graph $K_4$ are the only extremal graphs. We complete the proof of Theorem 1.1.

3. Conclusions

In this paper, we show that for $\lambda\in(0, 1]$ , unions of copies of the complete graph $K_4$ are optimal on the level of dissociation occupancy fraction among all cubic graphs, which implies that a union of copies of the complete graph $K_4$ maximizes the number of dissociation sets and the dissociation polynomial for $\lambda\in(0, 1]$ of a cubic graph on the same number of vertices.

Acknowledgments

The work is supported by Research Foundation for Advanced Talents of Beijing Technology and Business University (No. 19008022331).

Conflict of interest

We declare that there are no conflicts of interest.

Appendix A. The expressions for $\beta_{C}(\lambda)$ , $\beta_{0}^{v}(C)$ , $\beta_{1}^{v}(C)$ , $\beta_{0}^{u}(C)$ and $\beta_{1}^{u}(C)$ , and all configurations $C\in \mathcal{C}$ .

We write the expressions for $\beta_{C}(\lambda)$ , $\beta_{0}^{v}(C)$ , $\beta_{1}^{v}(C)$ , $\beta_{0}^{u}(C)$ and $\beta_{1}^{u}(C)$ :

$\begin{aligned} D_{C}(\lambda)& = \lambda^{{a_{1}}^{'}}\cdot (\lambda+a_{2}\lambda^{2}+D_{H}(\lambda)), \\ \beta_{C}(\lambda)& = \frac{\lambda^{{a_{1}}^{'}}}{D_{C}(\lambda)}\cdot(\lambda+a_{2}\lambda^{2}), \\ \beta_{0}^{v}(C)& = \frac{\lambda^{{a_{1}}^{'}}}{D_{C}(\lambda)}\cdot\lambda, \\ \beta_{1}^{v}(C)& = \frac{\lambda^{{a_{1}}^{'}}}{D_{C}(\lambda)}\cdot a_{2}\lambda^{2}, \\ \beta_{0}^{u}(C)& = \frac{1}{3}\cdot\frac{\lambda^{{a_{1}}^{'}}}{D_{C}(\lambda)}\cdot\sum\limits_{u \in A_{2}} \sum\limits_{D\in\mathcal{D}(H-N(u))}\lambda^{1+|D|}, \\ \beta_{1}^{u}(C)& = \frac{1}{3}\cdot\frac{\lambda^{{a_{1}}^{'}}}{D_{C}(\lambda)}\cdot( \sum\limits_{u \in A_{1}} \sum\limits_{D\in\mathcal{D}(H-N(u))}\lambda^{1+|D|}+ \sum\limits_{u \in A_{2}} \sum\limits_{x\in N(u)} \bf{1}_{x\notin A_{1}}\sum\limits_{D\in\mathcal{D}(A_{2}\backslash (N(u)\cup N(x)))}\lambda^{2+|D|}). \end{aligned}$

For all configurations $C\in \mathcal{C}$ , their accurate expressions are computed and listed as follows.

$\begin{array}{l} {\bf C_{1}(0, 0, 3):\ } \beta_{C}(\lambda) & = \frac{\lambda+3 \lambda^2}{1+4 \lambda+6 \lambda^{2}+\lambda^{3}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+6 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{v}(C) = \frac{3 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}+\lambda^{3}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{3 \lambda+ 6 \lambda^{2}+3 \lambda^{3}}{1+4 \lambda+6 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{3 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}+\lambda^{3}}. \\ {\bf C_{2}(0, 0, 3):\ } \beta_{C}(\lambda) & = \frac{\lambda+3 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}+\lambda^{3}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+6 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{v}(C) = \frac{3 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}+\lambda^{3}}, \end{array}$

$\begin{array}{l} \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{3 \lambda+ 4 \lambda^{2}+\lambda^{3}}{1+4 \lambda+6 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{5 \lambda^{2}+2 \lambda^{3}}{1+4 \lambda+6 \lambda^{2}+\lambda^{3}}.\\ {\bf C_{3}(0, 0, 3):\ } \beta_{C}(\lambda) & = \frac{\lambda+3 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+6 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{3 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{3 \lambda+ 2 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{7 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}}.\\ {\bf C_{4}(0, 0, 3):\ } \beta_{C}(\lambda) & = \frac{\lambda+3 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+6 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{3 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}}, \end{array}$

$\begin{array}{l} \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{3 \lambda}{1+4 \lambda+6 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{9 \lambda^{2}}{1+4 \lambda+6 \lambda^{2}}.\\ {\bf C_{5}(1, 1, 2):\ } \beta_{C}(\lambda) & = \frac{\lambda+2 \lambda^{2}}{1+4 \lambda+5 \lambda^{2}+\lambda^{3}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+5 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{v}(C) = \frac{2 \lambda^{2}}{1+4 \lambda+5 \lambda^{2}+\lambda^{3}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{2 \lambda+ 4 \lambda^{2}+2 \lambda^{3}}{1+4 \lambda+5 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{\lambda+4 \lambda^{2}+ \lambda^{3}}{1+4 \lambda+5 \lambda^{2}+\lambda^{3}}. \end{array}$

$\begin{array}{l} {\bf C_{6}(1, 1, 2):\ } \beta_{C}(\lambda) & = \frac{\lambda+2 \lambda^{2}}{1+4 \lambda+4 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+4 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{2 \lambda^{2}}{1+4 \lambda+4 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{2 \lambda+ 3 \lambda^{2}}{1+4 \lambda+4 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{\lambda+3 \lambda^{2}}{1+4 \lambda+4 \lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{7}(1, 1, 2):\ } \beta_{C}(\lambda) & = \frac{\lambda+2 \lambda^{2}}{1+4 \lambda+4 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+4 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{2 \lambda^{2}}{1+4 \lambda+4 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{2 \lambda+ \lambda^{2}}{1+4 \lambda+4 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{\lambda+5 \lambda^{2}}{1+4 \lambda+4 \lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{8}(1, 1, 2):\ } \beta_{C}(\lambda) & = \frac{\lambda+2 \lambda^{2}}{1+4 \lambda+5 \lambda^{2}+\lambda^{3}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+5 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{v}(C) = \frac{2 \lambda^{2}}{1+4 \lambda+5 \lambda^{2}+\lambda^{3}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{2 \lambda+2 \lambda^{2}}{1+4 \lambda+5 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{\lambda+6 \lambda^{2}+3 \lambda^{3}}{1+4 \lambda+5 \lambda^{2}+\lambda^{3}}. \end{array}$

$\begin{array}{l} {\bf C_{9}(1, 2, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{\lambda+2 \lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda+3 \lambda^{2}}{1+4 \lambda+3 \lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{10}(1, 2, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{\lambda+2 \lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda+3 \lambda^{2}}{1+4 \lambda+3 \lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{11}(1, 2, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+4 \lambda+2 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+2 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+4 \lambda+2 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{\lambda+ \lambda^{2}}{1+4 \lambda+2 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda+2 \lambda^{2}}{1+4 \lambda+2 \lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{12}(1, 2, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+4 \lambda+\lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+\lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+4 \lambda+\lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{\lambda}{1+4 \lambda+\lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda+ \lambda^{2}}{1+4 \lambda+\lambda^{2}}.\\ {\bf C_{13}(2, 2, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+4 \lambda+4 \lambda^{2}+\lambda^{3}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+4 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+4 \lambda+4 \lambda^{2}+\lambda^{3}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{\lambda+2 \lambda^{2}+\lambda^{3}}{1+4 \lambda+4 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda+5 \lambda^{2}+2 \lambda^{3}}{1+4 \lambda+4 \lambda^{2}+\lambda^{3}}. \end{array}$

$\begin{array}{l} {\bf C_{14}(2, 2, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{\lambda+2 \lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda+3 \lambda^{2}}{1+4 \lambda+3 \lambda^{2}}.\\ {\bf C_{15}(2, 2, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{\lambda+\lambda^{2}}{1+4 \lambda+3 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda+4 \lambda^{2}}{1+4 \lambda+3 \lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{16}(2, 2, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+4 \lambda+2 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+2 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+4 \lambda+2 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{\lambda}{1+4 \lambda+2 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda+3 \lambda^{2}}{1+4 \lambda+2 \lambda^{2}}.\\ {\bf C_{17}(1, 3, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+4 \lambda}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda}, \quad \beta_{1}^{v}(C) = 0, \quad \beta_{0}^{u}(C) = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{3 \lambda}{1+4 \lambda}. \end{array}$

$\begin{array}{l} {\bf C_{18}(1, 3, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+4 \lambda}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda}, \quad \beta_{1}^{v}(C) = 0, \quad \beta_{0}^{u}(C) = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{3 \lambda}{1+4 \lambda}.\\ {\bf C_{19}(2, 3, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+4 \lambda+2 \lambda^{2}}, \ \ \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+2 \lambda^{2}}, \quad \beta_{1}^{v}(C) = 0, \\ \beta_{0}^{u}(C) & = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{3 \lambda+4 \lambda^{2}}{1+4 \lambda+2 \lambda^{2}}.\\ {\bf C_{20}(2, 3, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+4 \lambda+2\lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+2\lambda^{2}}, \quad \beta_{1}^{v}(C) = 0, \\ \beta_{0}^{u}(C) & = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{3 \lambda+4 \lambda^{2}}{1+4 \lambda+2\lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{21}(2, 3, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+4 \lambda+\lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+\lambda^{2}}, \quad \beta_{1}^{v}(C) = 0, \\ \beta_{0}^{u}(C) & = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{3 \lambda+2 \lambda^{2}}{1+4 \lambda+\lambda^{2}}.\\ {\bf C_{22}(3, 3, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+4 \lambda+3 \lambda^{2}+\lambda^{3}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+3 \lambda^{2}+\lambda^{3}}, \quad \beta_{1}^{v}(C) = 0, \\ \beta_{0}^{u}(C) & = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{3 \lambda+6 \lambda^{2}+3 \lambda^{3}}{1+4 \lambda+3 \lambda^{2}+\lambda^{3}}.\\ {\bf C_{23}(3, 3, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+4 \lambda+2\lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+4 \lambda+2\lambda^{2}}, \quad \beta_{1}^{v}(C) = 0, \\ \beta_{0}^{u}(C) & = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{3 \lambda+4 \lambda^{2}}{1+4 \lambda+2\lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{24}(0, 0, 2):\ } \beta_{C}(\lambda) & = \frac{\lambda+2\lambda^{2}}{1+3 \lambda+3 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+3 \lambda+3 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{2\lambda^{2}}{1+3 \lambda+3 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{2 \lambda+2 \lambda^{2}}{1+3 \lambda+3 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda^{2}}{1+3 \lambda+3 \lambda^{2}}.\\ {\bf C_{25}(0, 0, 2):\ } \beta_{C}(\lambda) & = \frac{\lambda+2\lambda^{2}}{1+3 \lambda+3\lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+3 \lambda+3\lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{2\lambda^{2}}{1+3 \lambda+3\lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{2 \lambda}{1+3 \lambda+3\lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{4 \lambda^{2}}{1+3 \lambda+3\lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{26}(1, 1, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+3 \lambda+2 \lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+3 \lambda+2 \lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+3 \lambda+2 \lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{ \lambda +\lambda^{2}}{1+3 \lambda+2 \lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{\lambda+2 \lambda^{2}}{1+3 \lambda+2 \lambda^{2}}.\\ {\bf C_{27}(1, 1, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+3 \lambda+3\lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+3 \lambda+3\lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+3 \lambda+3\lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{ \lambda}{1+3 \lambda+3\lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{\lambda+\lambda^{2}}{1+3 \lambda+3\lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{28}(1, 2, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+3 \lambda}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+3 \lambda}, \quad \beta_{1}^{v}(C) = 0, \quad \beta_{0}^{u}(C) = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda}{1+3 \lambda}.\\ {\bf C_{29}(1, 2, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+3 \lambda}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+3 \lambda}, \quad \beta_{1}^{v}(C) = 0, \quad \beta_{0}^{u}(C) = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda}{1+3 \lambda}.\\ {\bf C_{30}(2, 2, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+3 \lambda+\lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+3 \lambda+\lambda^{2}}, \quad \beta_{1}^{v}(C) = 0, \\ \beta_{0}^{u}(C)& = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda+2 \lambda^{2}}{1+3 \lambda+\lambda^{2}}. \end{array}$

$\begin{array}{l} {\bf C_{31}(2, 2, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+3 \lambda}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+3 \lambda}, \quad \beta_{1}^{v}(C) = 0, \quad \beta_{0}^{u}(C) = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{2 \lambda}{1+3 \lambda}.\\ {\bf C_{32}(0, 0, 1):\ } \beta_{C}(\lambda) & = \frac{\lambda+\lambda^{2}}{1+2 \lambda+\lambda^{2}}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+2 \lambda+\lambda^{2}}, \quad \beta_{1}^{v}(C) = \frac{\lambda^{2}}{1+2 \lambda+\lambda^{2}}, \\ \beta_{0}^{u}(C) & = \frac{1}{3} \cdot\frac{\lambda}{1+2 \lambda+\lambda^{2}}, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{ \lambda^{2}}{1+2 \lambda+\lambda^{2}}.\\ {\bf C_{33}(1, 1, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+2 \lambda}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+2 \lambda}, \quad \beta_{1}^{v}(C) = 0, \quad \beta_{0}^{u}(C) = 0, \quad \beta_{1}^{u}(C) = \frac{1}{3} \cdot\frac{\lambda}{1+2 \lambda}.\\ {\bf C_{34}(0, 0, 0):\ } \beta_{C}(\lambda) & = \frac{\lambda}{1+\lambda}, \quad \beta_{0}^{v}(C) = \frac{\lambda}{1+\lambda}, \quad \beta_{1}^{v}(C) = 0, \quad \beta_{0}^{u}(C) = 0, \quad \beta_{1}^{u}(C) = 0. \end{array}$

References

[1]	J. Cutler, A. J. Radcliffe, Minimizing the number of independent sets in triangle-free regular graphs, Discrete Math., 341 (2018), 793–800. https://doi.org/10.1016/j.disc.2017.11.016 doi: 10.1016/j.disc.2017.11.016
[2]	E. Davies, M. Jenssen, W. Perkins, B. Roberts, Independent sets, matchings, and occupancy fractions, J. Lond. Math. Soc., 96 (2017), 47–66. https://doi.org/10.1112/jlms.12056
[3]	E. Davies, M. Jenssen, W. Perkins, B. Roberts, Extremes of the internal energy of the Potts model on cubic graphs, Random Struct. Algor., 53 (2018), 59–75. https://doi.org/10.1002/rsa.20767 doi: 10.1002/rsa.20767
[4]	D. Galvin, P. Tetali, On weighted graph homomorphisms, Discrete Math. Theor. Comput. Sci., 63 (2004), 97–104. https://doi.org/10.1090/dimacs/063/07 doi: 10.1090/dimacs/063/07
[5]	J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput., 10 (2001), 219–237. https://doi.org/10.1017/S0963548301004631 doi: 10.1017/S0963548301004631
[6]	G. Perarnau, W. Perkins, Counting independent sets in cubic graphs of given girth, J. Combin. Theory Ser. B, 133 (2018), 211–242. https://doi.org/10.1016/j.jctb.2018.04.009 doi: 10.1016/j.jctb.2018.04.009
[7]	M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput., 10 (1981). https://doi.org/10.1137/0210022
[8]	Y. F. Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput., 19 (2010), 315–320. https://doi.org/10.1017/S0963548309990538 doi: 10.1017/S0963548309990538

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

AIMS Mathematics

1.8 3.4

Metrics

Article views(1634) PDF downloads(123) Cited by(0)

Preview PDF

Download XML

Export Citation

Article outline

Show full outline

Figures and Tables

Figures(2) / Tables(1)

AIMS Mathematics

Counting the number of dissociation sets in cubic graphs

Related Papers:

Abstract

1. Introduction

2. Proof of Theorem 1.1

3. Conclusions

Acknowledgments

Conflict of interest

Appendix A. The expressions for $\beta_{C}(\lambda)$ , $\beta_{0}^{v}(C)$ , $\beta_{1}^{v}(C)$ , $\beta_{0}^{u}(C)$ and $\beta_{1}^{u}(C)$ , and all configurations $C\in \mathcal{C}$ .

References

Reader Comments

通讯作者: 陈斌, bchen63@163.com

Metrics

Figures and Tables

Other Articles By Authors

Catalog

AIMS Mathematics

Counting the number of dissociation sets in cubic graphs

Related Papers:

Abstract

1. Introduction

2. Proof of Theorem 1.1

3. Conclusions

Acknowledgments

Conflict of interest

Appendix A. The expressions for βC(λ) \beta_{C}(\lambda) , βv0(C) \beta_{0}^{v}(C) , βv1(C) \beta_{1}^{v}(C) , βu0(C) \beta_{0}^{u}(C) and βu1(C) \beta_{1}^{u}(C) , and all configurations C∈C C\in \mathcal{C} .

References

Reader Comments

通讯作者: 陈斌, bchen63@163.com

Metrics

Figures and Tables

Other Articles By Authors

Related pages

Tools

Export File

Citation

Format

Content

Catalog

Appendix A. The expressions for $\beta_{C}(\lambda)$ , $\beta_{0}^{v}(C)$ , $\beta_{1}^{v}(C)$ , $\beta_{0}^{u}(C)$ and $\beta_{1}^{u}(C)$ , and all configurations $C\in \mathcal{C}$ .