Permanent index of matrices associated with graphs

Publication date 17 February 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.00810, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p25

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

matrix permanent index total weighting

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Abstract: A total weighting of a graph

G

is a mapping

f

which assigns to each element

z i n V (G) c u p E (G)

a real number

f (z)

as its weight. The vertex sum of

v

with respect to

f

is

p h i_{f} (v) = s u m_{e i n E (v)} f (e) + f (v)

. A total weighting is proper if

p h i_{f} (u) e p h i_{f} (v)

for any edge

u v

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) i n L (z)

for each

z i n V (G) c u p 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 oindent{{�f Key words: } Permanent index, matrix, total weighting}

Review text

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.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Permanent index of matrices associated with graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510339)