|
Tutte Polynomial of Tensor Product Graph and Its Applications
YANG Gang, LIAO Yunhua
Acta Mathematicae Applicatae Sinica
2023, 46 (4):
507-521.
Let $G$ be a connected graph with $m$ edges. $\mathcal{H}=\{H_1,H_2,\cdots,H_m\}$ is a set of disjoint graphs. $H_i$ is a connected graph with two distinct vertices $u_i$ and $v_i$, $i=1,2,\cdots,m$. The tensor product of $G$ and $\mathcal{H}$, denoted by $G[\mathcal{H}]$, is the graph obtained from $G$ by replacing edge $e_i$ of $G$ with $H_i$ for $1\leq i\leq m$. In this paper, only using classical graph theory, we obtain a formula for the Tutte polynomial of the tensor product $G[\mathcal{H}]$. Firstly, we divide the set of spanning subgraphs of $H_i$ into two disjoint subsets according to whether the two distinct vertices $u_i$ and $v_i$ are contained in the same connected component or not. In this way, we split the Tutte polynomial of $H$ into two parts, $T_1(H;x,y)$ and $T_2(H;x,y)$. By using the connection between the subgraphs of $H$ and that of $H/uv$, we derive expressions for $T_1(H;x,y)$ and $T_2(H;x,y)$ in terms of $T(H;x,y)$ and $T(H/uv;x,y)$. Secondly, we partition the set of spanning subgraphs of $G[\mathcal{H}]$ into $2^{|E(G)|}$ disjoint subsets according to the construction method of $G[\mathcal{H}]$. Applying an indirect way, we obtain a formula for the contribution to $T(G[\mathcal{H}];x,y)$ of each subset. Thirdly, we sum over the contribution of each subset and obtain an expression for $T(G[\mathcal{H}];x,y)$. As applications, we show that the Tutte polynomials of several operation graphs can be deduced from our result directly. Finally, we discuss why our method can work well and in which situation our technique can be applied to study graph polynomials.
Reference |
Related Articles |
Metrics |
Comments(0)
|
|