\documentclass[12pt]{article} \usepackage{epsfig} \usepackage{latexsym} \usepackage{graphicx} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{color} \def \red {\textcolor{red} } \def \bl {\textcolor{blue} } \def \gr {\textcolor{green} } \sloppy \setlength{\oddsidemargin}{0.25 in} \setlength{\evensidemargin}{0.25 in} \setlength{\topmargin}{0.5 in} %%%%%FOR X. ZHU %\setlength{\topmargin}{-0.4 in} %%%%%FOR OTHERS \setlength{\textwidth}{6 in} \setlength{\textheight}{8.1 in} \parskip=6pt plus2pt \newtheorem{theorem}{Theorem} \newtheorem{proposition}{Proposition} \newtheorem{definition}{Definition} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \newtheorem{conjecture}{Conjecture} \newtheorem{question}{Question} \newtheorem{example}{Example} \newtheorem{claim}{Claim} \newtheorem{observation}{Observation} \newcommand{\perrank}{{\rm perrank}} \newcommand{\pind}{{\rm pind}} \newcommand{\per}{{\rm per}} \newcommand{\pp}{{\rm per}} \newcommand{\oversign}{\hfill\rule{0.5em}{0.809em}} \newcommand{\qed}{\hfill\rule{0.5em}{0.809em}} \newcommand{\ppmod}[1]{\hspace{-3mm}\pmod{#1}} \newcommand{\sign}{{\rm sign}} \def\bar{\overline} \newenvironment{proof}{ \par \noindent {\bf Proof.}\rm}{\mbox{}\hfill\rule{0.5em}{0.809em}\par} \begin{document} \title{Permanent index of matrices associated with graphs} \author{ Tsai-Lien Wong \thanks{Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 80424. Grant numbers: MOST 104-2115-M-110 -001 -MY2. Email: tlwong@math.nsysu.edu.tw} \and Xuding Zhu \thanks{Department of Mathematics, Zhejiang Normal University, China. Grant Numbers: NSF11171310 and ZJNSF Z6110786. Email: xudingzhu@gmail.com. } \\[0.2cm] } \date{} \maketitle \begin{abstract} 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) \ne \phi_f(v)$ for any edge $uv$ of $G$. A $(k,k')$-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'$ permissible weights. We say $G$ is $(k,k')$-choosable if for any $(k,k')$-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 [T. Wong and X. Zhu, Total weight choosability of graphs, J. Graph Theory 66 (2011), 198-212] 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. \end{abstract} {\small \noindent{{\bf Key words: } Permanent index, matrix, total weighting} \section{Introduction} A {\em 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. Given a total weighting $f$ of $G$, for a vertex $v$ of $G$, the {\em vertex sum} of $v$ with respect to $f$ is defined as $\phi_f(v)=\sum_{e \in E(v)}f(e)+f(v)$. A total weighting is proper if $\phi_f$ is a proper colouring of $G$, i.e., for any edge $uv$ of $G$, $\phi_f(u) \ne \phi_f(v)$. A total weighting $\phi$ with $\phi(v)=0$ for all vertices $v$ is also called an {\em edge weighting}. A proper edge weighting $\phi$ with $\phi(e) \in \{1,2,\ldots, k\}$ for all edges $e$ is called a {\em vertex colouring $k$-edge weighting} of $G$. Karonski, {\L}uczak and Thomason \cite{KLT2004} first studied edge weighting of graphs. They conjectured that every graph with no isolated edges has a vertex colouring $3$-edge weighting. This conjecture received considerable attention, and is called the 1-2-3 conjecture. Addario-Berry, Dalal, McDiarmid, Reed and Thomason \cite{Add2007} proved that every graph with no isolated edges has a vertex colouring $k$-edge weighting for $k=30$. The bound $k$ was improved to $k = 16$ by Addario-Berry, Dalal and Reed in \cite{Add2005} and to $k = 13$ by Wang and Yu in \cite{yu}, and to $k=5$ by Kalkowski \cite{K}. Total weighting of graphs was first studied by Przyby{\l}o and Wo\'{z}niak in \cite{PW2010}, where they defined $\tau(G)$ to be the least integer $k$ such that $G$ has a proper total weighting $\phi$ with $\phi(z) \in \{1,2, \ldots, k\}$ for $z \in V(G) \cup E(G)$. They proved that $\tau(G) \le 11$ for all graphs $G$, and conjectured that $\tau(G)=2$ for all graphs $G$. This conjecture is called the 1-2 conjecture. A breakthrough on 1-2 conjecture was obtained by Kalkowski, Karo\'{n}ski and Pfender in \cite{KKP10}, where it was proved that every graph $G$ has a proper total weighting $\phi$ with $\phi(v) \in \{1,2\}$ for $v \in V(G)$ and $\phi(e) \in \{1,2,3\}$ for $e \in E(G)$. The list version of edge weighting of graphs was introduced by Bartnicki, Grytczuk and Niwczyk in \cite{BGN09}, and the list version of total weighting of graphs was introduced independently by Wong and Zhu in \cite{WZ11} and by Przyby{\l}o and Wo\'{z}niak \cite{PW2011}. Suppose $\psi: V(G) \cup E(G) \to \{1,2,\ldots,\}$ is a mapping which assigns to each vertex and each edge of $G$ a positive integer. A $\psi$-list assignment of $G$ is a mapping $L$ which assigns to $z \in V(G) \cup E(G)$ a set $L(z)$ of $\psi(z)$ real numbers. Given a total list assignment $L$, a proper $L$-total weighting is a proper total weighting $\phi$ with $\phi(z) \in L(z)$ for all $z \in V(G) \cup E(G)$. We say $G$ is {\em total weight $\psi$-choosable} if for any $\psi$-list assignment $L$, there is a proper $L$-total weighting of $G$. We say $G$ is $(k,k')$-choosable if $G$ is $\psi$-total weight choosable, where $\psi(v)=k$ for $v \in V(G)$ and $\psi(e) = k'$ for $e \in E(G)$. As strengthening of the 1-2-3 conjecture and the 1-2 conjecture, it was conjectured in \cite{WZ11} that every graph with no isolated edges is $(1,3)$-choosable and every graph is $(2,2)$-choosable. Thes two conjectures received a lot of attention and are verified for some special classes of graphs. In particular, it was shown in \cite{ZW2014} that every graph is $(2,3)$-choosable. A promising tool in the study of these conjectures is Combinatorial Nullstellensatz. For each $z \in V(G) \cup E(G)$, let $x_z$ be a variable associated to $z$. Fix an orientation $D$ of $G$. Consider the polynomial $$P_G(\{x_z: z \in V(G) \cup E(G)\}) = \prod_{e=uv \in E(D)}\left( \left(\sum_{e \in E(v)} x_e+ x_v\right) - \left(\sum_{e \in E(u)} x_e+ x_u\right)\right).$$ Assign a real number $\phi(z)$ to the variable $x_z$, and view $\phi(z)$ as the weight of $z$. Let $P_G( \phi )$ be the evaluation of the polynomial at $x_z = \phi(z)$. Then $\phi$ is a proper total weighting of $G$ if and only if $P_G( \phi) \ne 0$. Note that $P_G$ has degree $|E(G)|$. An {\em index function} of $G$ is a mapping $\eta$ which assigns to each vertex or edge $z$ of $G$ a non-negative integer $\eta(z)$ and an index function $\eta$ is {\em valid} if $\sum_{z \in V(G) \cup E(G)}\eta(z)=|E(G)|$. For a valid index function $\eta$, let $c_{\eta}$ be the coefficient of the monomial $\prod_{z \in V \cup E} x_{z}^{\eta(z)}$ in the expansion of $P_G$. It follows from Combinatorial Nullstellensatz \cite{nullstellensatz,AlonTarsi} that if $c_{\eta} \ne 0$, and $L$ is a list assignment which assigns to each $z \in V(G) \cup E(G)$ a set $L(z)$ of $ \eta(z)+1$ real numbers, then there exists a mapping $\phi$ with $\phi(z) \in L(z)$ such that $$P_G(\phi) \ne 0.$$ So to prove a graph $G$ is $(k,k')$-choosable, it suffices to show that there is a valid index function $\eta$ with $\eta(v) \le k-1$ for $v \in V(G)$, $\eta(e) \le k'-1$ for $e \in E(G)$ and $c_{\eta} \ne 0$. We write the polynomial $P_G(\{x_z: z \in V(G) \cup E(G)\})$ as $$P_G(\{x_z: z \in V(G) \cup E(G)\}) = \prod_{e \in E(D)}\sum_{z \in V(G) \cup E(G)}A_G[e,z]x_z.$$ It is straightforward to verify that for $e \in E(G)$ and $z \in V(G) \cup E(G)$, if $e=(u,v)$ (oriented from $u$ to $v$), then \begin{equation*} A_G[e,z]= \begin{cases} 1 & \text{if $z=v$, or $z \ne e$ is an edge incident to $v$,} \\ -1 & \text{if $z=u$, or $z \ne e$ is an edge incident to $u$,} \\ 0 &\text{otherwise.} \end{cases} \end{equation*} Now $A_G $ is a matrix, whose rows are indexed by the edges of $G$ and the columns are indexed by edges and vertices of $G$. Let $B_G$ be the submatrix of $A_G$ consisting of those columns of $A_G$ indexed by edges. It turns out that $(k,k')$-choosability of a graph $G$ is related to the permanent indices of $A_G$ and $B_G$. For an $m \times m$ matrix $A$ (whose entries are reals), the {\em permanent} of $A$ is defined as $${\rm per}(A)=\sum_{\sigma \in S_m} \prod_{i=1}^mA[i, \sigma(i)]$$ where $S_m$ is the symmetric group of order $m$, i.e., the summation is taken over all the permutations $\sigma$ over $\{1,2,\ldots, m\}$. The {\em permanent index} of a matrix $A$, denoted by $\pind(A)$, is the minimum integer $k$ such that there is a matrix $A'$ such that $\per(A') \ne 0$, each column of $A'$ is a column of $A$ and each column of $A$ occurs in $A'$ at most $k$ times (if such an integer $k$ does not exist, then $\pind(A)=\infty$). Consider the matrix $A_G$ defined above. Given a vertex or edge $z$ of $G$, let $A_G(z)$ be the column of $A_G$ indexed by $z$. For an index function $\eta$ of $G$, let $A_G(\eta)$ be the matrix, each of its column is a column of $A_G$, and each column $A_G(z)$ of $A_G$ occurs $\eta(z)$ times as a column of $A_G(\eta)$. It is known \cite{alontarsi1989, WZ11} and easy to verify that for a valid index function $\eta$ of $G$, $c_{\eta} \ne 0$ if and only if $\per(A_G(\eta)) \ne 0$. Thus if $\pind(A_G) =1$, then $G$ is $(2,2)$-choosable; if $\pind(B_G) \le 2$, then $G$ is $(1,3)$-choosable. The following two conjectures are proposed in \cite{WZ11}: \begin{conjecture} \cite{BGN09} \label{g0} For any graph $G$ with no isolated edges, $\pind(B_G) \le 2$. \end{conjecture} \begin{conjecture}\cite{WZ11} \label{g1} For any graph $G$, $\pind(A_G) = 1$. \end{conjecture} The discussion above shows that Conjecture \ref{g0} implies that any graph without isolated edges is $(1,3)$-choosable, and Conjecture \ref{g1} implies that every graph is $(2,2)$-choosable. We say an index function $\eta$ is {\em non-singular} if there is a valid index function $\eta' \le \eta$ with $\per(A_G(\eta')) \ne 0$. In this paper, we are interested in non-singularity of index functions $\eta$ for which $\eta(e)=1$ for every edge $e$ and $\eta(v)$ can be any non-negative integers for any every vertex $v$. Assume $\eta$ is such an index function of $G$. We delete a vertex $v$, and construct an index function $\eta'$ for $G-v$ from the restriction of $\eta$ to $G-v$ by doing the following modification: $\eta(v)$ of the neighbours $u$ of $v$ have $\eta'(u)=\eta(u)+1$, and all the other neighbours $u$ of $v$ (if any) have $\eta'(u) = \eta(u)-1$. We prove that if $\eta'$ is a non-singular index function of $G-v$, then $\eta$ is a non-singular index function of $G$. Applying this reduction method, we prove that Conjecture \ref{g1} holds for subcubic graphs, $2$-trees, Halin graphs and grids. Consequently, subcubic graphs, $2$-trees, Halin graphs and grids are $(2, 2)$-choosable. \section{Reduction to induced subgraphs} \label{sec:reduction} To study non-singularity of index functions of $G$, we shall consider matrices whose columns are linear combinations of columns of $A_G$. Assume $A$ is a square matrix whose columns are linear combinations of columns of $A_G$. Define an index function $\eta_A: V(G) \cup E(G) \to \{0,1, \ldots, \}$ as follows: For $z \in V(G) \cup E(G)$, $\eta_A(z)$ is the number of columns of $A$ in which $A_G(z)$ appears with nonzero coefficient. It is known \cite{WZ11} that columns of $A_G$ are not linearly independent. In particular, if $e=uv$ is an edge of $G$, then $$A_G(e) = A_G(u)+A_G(v) \eqno(1)$$ Thus a column of $A$ may have different ways to be expressed as linear combinations of columns of $A_G$. So the index function $\eta_A$ is not uniquely determined by $A$. Instead, it is determined by the way we choose to express the columns of $A$ as linear combinations of columns of $A_G$. For simplicity, we use the notation $\eta_A$, however, whenever the function $\eta_A$ is used, an explicit expression of the columns of $A$ as linear combinations of columns of $A_G$ is given, and we refer to that specific expression. It is well-known (and follows easily from the definition) that the permanent of a matrix is multi-linear on its column vectors and row vectors: If a column $C$ of $A$ is a linear combination of two columns vectors $C =\alpha C'+ \beta C''$, and $A'$ (respectively, $A''$) is obtained from $A$ by replacing the column $C$ with $C'$ (respectively, with $C''$), then $${\rm per}(A) = \alpha\ {\rm per}(A') + \beta \ {\rm per}(A''). \eqno(2)$$ By using (2) repeatedly, one can find matrices $A_1, A_2, \ldots, A_q$ and real numbers $a_1, a_2, \ldots, a_q$ such that $$\per(A) = \sum_{j=1}^q a_j \per(A_j)$$ where each $A_j$ is a square matrix consisting of columns of $A_G$, with each column $A_G(z)$ appears at most $\eta(z)$ times. Thus if $\per(A) \ne 0$, then one of the $\per(A_j) \ne 0$. Thus if $\per(A) \ne 0$, then $\eta_A$ is a non-singular index function of $G$. \begin{theorem} \label{del} Suppose $G$ is a graph, $\eta$ is an index function of $G$ for which $\eta(e)=1$ for every edge $e$. Let $v$ be a vertex of $G$. Let $\eta'$ be obtained from the restriction of $\eta$ to $G-v$ by the following modification: Choose $d_G(v)-\eta(v)$ neighbours $u$ of $v$ with $\eta(u) \ge 1$, and let $\eta'(u)=\eta(u)-1$. For the other $\eta(v)$ neighbours $u$ of $v$, let $\eta'(u)=\eta(u)+1$. If $\eta'$ is a non-singular index function of $G-v$, then $\eta$ is a non-singular index function of $G$. \end{theorem} Theorem \ref{del} follows from the following more general statement. \begin{theorem} \label{del2} Suppose $G$ is a graph, $v$ is a vertex of $G$ and $E(v)=\{e_1, e_2,\ldots, e_k\}$, with $e_i=vv_i$ for $i=1,2,\ldots,k$. Assume $\eta$ is an index function of $G$. Here $\eta(e)$ can be any non-negative integer. Choose a subset $J$ of $\{1,2,\ldots, k \}$ and integers $1 \le k_i \le \min\{\eta(e_i), \eta(v_i)\}$ such that $\eta(v) + \sum_{i \in J} k_i = k$. Let $\eta'$ be the index function of $G' = G- v$ which is equal to the restriction of $\eta$ to $G-v$, except that \begin{enumerate} \item For $i \in J$, $\eta'(v_i) = \eta(v_i) - k_i$. \item For $i \in \{1,2,\ldots, k\} \setminus J$, $\eta'(v_i) = \eta(v_i)+ \eta(e_i)$. \end{enumerate} If $\eta'$ is a non-singular index function for $G'$, then $\eta$ is a non-singular index function for $G$. \end{theorem} \begin{proof} Assume $\eta'$ is non-singular. Let $\eta'' \le \eta'$ be a valid index function with $\per(A_{G'}(\eta'')) \ne 0$. Assume $|E(G)|=m$ and $|E(G')|=m' = m -k$. By viewing each vertex and each edge of $G'$ as a vertex and an edge of $G$, $A_G(\eta'')$ is an $m \times m'$ matrix, consisting $m'$ columns of $A_G$. First we extend $A_G(\eta'')$ into an $m \times m$ matrix $A$ by adding $k$ copies of the column $A_G(v)$. The added $k$ columns has $k$ rows (the rows indexed by edges incident to $v$) that are all $1$'s (with all these edges oriented towards $v$), and all the other entries of these $k$ columns are $0$. Therefore $\per(M) = \per(A_{G'}(\eta'')) k !$, and hence $\per(M) \ne 0$. Starting from the matrix $M$, for each $i\in \{1,2,\ldots, k\} \setminus J$, remove $\min\{\eta(e_i), \eta''(v_i)\}$ copies of the column $A_G(v_i)$ and add $\min\{\eta(e_i), \eta''(v_i)\}$ copies of the column $A_G(e_i)$. Denote by $M'$ the resulting matrix. \begin{claim} For the matrix $M'$ constructed above, we have $\per(M') = \per(M)$. \end{claim} \begin{proof} Since by (1), $A_G(e_i) = A_G(v_i) + A_G(v)$, we re-write $\min\{\eta(e_i), \eta''(v_i)\}$ copies of the column $A_G(e_i)$ of $M'$ as $A_G(v) + A_G(v_i)$. Then we expand the permanent using its multilinear property (i.e. using (2) repeatedly), to obtain the following equation: $$\per(M')=\per(M)+ \sum_{M''} \per(M'')$$ where $M''$ are those matrices which contain at least $k+1$ copies of the column $A_G(v)$. Since these $k+1$ columns has all $1$'s in $k$ rows and $0$ in all other entries, we have $\per(M'') = 0$ for all $M''$, and so $\per(M') = \per(M)$. \end{proof} For each $i \in J$, write $k_i$ copies of $A_G(v)$ in $M'$ as $A_G(e_i)-A_G(v_i)$. Note that this step does not change the matrix, since $A_G(v) = A_G(e_i)-A_G(v_i)$ (by (1)). Now each column of $M'$ is a linear combination of columns of $A_G$. We shall show that, with the linear combination of columns of $M'$ given in the above paragraph, $\eta_{M'}(z) \le \eta(z)$ for $z \in V(G) \cup E(G)$. If $z \notin \{e_i, v_i: i=1,2,\ldots, k\} \cup \{v\}$, $\eta_{M'}(z) = \eta_{M}(z) \le \eta''(z) \le \eta'(z) = \eta(z)$. If $i \in \{1,2,\ldots, k\} - J$, then $\eta_{M'}(e_i) = \min \{\eta(e_i), \eta''(v_i)\} \le \eta(e_i)$, and $ \eta_{M'}(v_i)=\eta_{M}(v_i) - \min \{\eta(e_i), \eta''(v_i)\} \le \max\{0,\eta''(v_i)-\eta(e_i)\} \le \eta'(v_i)-\eta(e_i)=\eta(v_i)$. If $i \in J$, then $\eta_{M'}(e_i) = k_i \leq \eta(e_i)$ and $\eta_{M'}(v_i)=\eta''(v_i)+k_i \le \eta'(v_i)+k_i = \eta(v_i)$. Finally, $\eta_{M'}(v)=k - \sum_{i \in J}k_i = \eta(v)$. As $\per(M') \ne 0$, we conclude that $\eta$ is a non-singular index function for $G$. This completes the proof of Theorem \ref{del2}. \end{proof} Theorem \ref{del} follows from Theorem \ref{del2} by choosing $k_i=1$ and $|J|=d(v)-\eta(v)$. By definition, if $\eta''$ is non-singular and $\eta' \ge \eta''$, then $\eta'$ is also non-singular. So the following is equivalent to Theorem \ref{del}. \begin{theorem} \label{del3} Suppose $G$ is a graph, $\eta$ is an index function of $G$ for which $\eta(e)=1$ for every edge $e$. Let $v$ be a vertex of $G$. Let $\eta'$ be obtained from the restriction of $\eta$ to $G-v$ by the following modification: Choose at least $d_G(v)-\eta(v)$ neighbours $u$ of $v$ with $\eta(u) \ge 1$, and let $\eta'(u)=\eta(u)-1$. For the other neighbours $u$ of $v$, let $\eta'(u)=\eta(u)+1$. If $\eta'$ is a non-singular index function of $G-v$, then $\eta$ is a non-singular index function of $G$. \end{theorem} We shall apply Theorem \ref{del3} repeatedly and delete a sequence of vertices in order. We need to record which vertices are deleted, and when a vertex is deleted, for which neighbours $u$ we have $\eta'(u)=\eta(u)+1$. For this purpose, instead of really removing the deleted vertices, we indicate the deletion of $v$ by orient all the edges incident to $v$ from $v$ to its neighbours, and then choose a subset of these oriented edges (to indicate those neighbours $u$ for which $\eta'(u)=\eta(u)+1$). The index function $\eta$ is changing in the process of the deletion. For convenience, we denote by $\eta_i$ the index function after the deletion of the $i$th vertex. In particular, $\eta_0=\eta$. Assume a vertex $v$ is deleted in the $i$th step, for each neighbour $u$ of $v$ (at the time $v$ is deleted), orient the edge as an arc from $v$ to $u$. After a sequence of vertices are deleted, we obtain a digraph $D$ formed by edges incident to the ``deleted" vertices. Let $D'$ be the sub-digraph ofˇ@ $D$ formed by those arcs $(v, u)$ with $u$ be the neighbour of $v$ (at the time $v$ is deleted) and for which we have $\eta'(u) = \eta(u)+1$. If $u$ is deleted in the $i$th step, then $d_{D'}^+(u) \le \eta_{i-1}(u)$. After the $i$th step, all edges incident to $u$ are oriented. On the other hand, $d_{D'}^-(u)$ is the number of indices $j