Permanent index of matrices associated with graphs (Q510339): Difference between revisions

Summary: A total weighting of a graph \(G\) is a mapping \(f\) which assigns to each element \(z \in V(G) \cup E(G)\) a real number \(f(z)\) as its weight. The vertex sum of \(v\) with respect to \(f\) is \(\phi_f(v)=\sum_{e \in E(v)}f(e)+f(v)\). A total weighting is proper if \(\phi_f(u) \neq \phi_f(v)\) for any edge \(uv\) of \(G\). A \((k,k^\prime)\)-list assignment is a mapping \(L\) which assigns to each vertex \(v\) a set \(L(v)\) of \(k\) permissible weights, and assigns to each edge \(e\) a set \(L(e)\) of \(k^\prime\) permissible weights. We say \(G\) is \((k,k^\prime)\)-choosable if for any \((k,k^\prime)\)-list assignment \(L\), there is a proper total weighting \(f\) of \(G\) with \(f(z) \in L(z)\) for each \(z \in V(G) \cup E(G)\). It was conjectured in [\textit{T. Wong} and \textit{X. Zhu}, J. Graph Theory 66, No. 3, 198--212 (2011; Zbl 1228.05161)] that every graph is \((2,2)\)-choosable and every graph with no isolated edge is \((1,3)\)-choosable. A promising tool in the study of these conjectures is Combinatorial Nullstellensatz. This approach leads to conjectures on the permanent indices of matrices \(A_G\) and \(B_G\) associated to a graph \(G\). In this paper, we establish a method that reduces the study of permanent of matrices associated to a graph \(G\) to the study of permanent of matrices associated to induced subgraphs of \(G\). Using this reduction method, we show that if \(G\) is a subcubic graph, or a 2-tree, or a Halin graph, or a grid, then \(A_G\) has permanent index \(1\). As a consequence, these graphs are \((2,2)\)-choosable.