% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.23}{22(3)}{2015}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins

\sloppy
% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Zeros of Jones polynomials of graphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Fengming Dong\thanks{Supported by NIE AcRf (RI 2/12 DFM).}\\
\small National Institute of Education\\[-0.8ex]
\small Nanyang Technological University\\[-0.8ex]
\small Singapore\\
\small\tt fengming.dong@nie.edu.sg
\and
Xian'an Jin\thanks{Corresponding author, supported by NSFC (No. 11271307).}\\
\small School of Mathematical Sciences\\[-0.8ex]
\small Xiamen University\\[-0.8ex]
\small P. R. China\\
\small\tt xajin@xmu.edu.cn
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Aug 25, 2014}{Jul 29, 2015}{Aug 14, 2015}\\
\small Mathematics Subject Classifications:  05C31, 57M27}

\begin{document}

\maketitle



\begin{abstract}
In this paper, we introduce the Jones polynomial of a graph $G=(V,E)$ with $k$ components as the following specialization of the Tutte
polynomial:
$$J_G(t)=(-1)^{|V|-k}t^{|E|-|V|+k}T_G(-t,-t^{-1}).$$
We first study its basic properties and determine certain extreme coefficients.
Then we prove that $(-\infty, 0]$ is a zero-free interval of Jones polynomials of connected bridgeless graphs while
for any small $\epsilon>0$ or large $M>0$, there is a zero of the Jones polynomial
of a plane graph in $(0,\epsilon)$, $(1-\epsilon,1)$, $(1,1+\epsilon)$ or $(M,+\infty)$. Let $r(G)$ be the
maximum moduli of zeros of $J_G(t)$. By applying Sokal's result on zeros of Potts model
partition functions and Lucas's theorem, we prove that
\begin{eqnarray*}
{q_s-|V|+1\over |E|}\leq r(G)<1+6.907652\Delta_G
\end{eqnarray*}
for any connected bridgeless and loopless graph $G=(V,E)$ of maximum
degree $\Delta_G$ with $q_s$ parallel classes.
As a consequence of the upper bound, X.-S. Lin's conjecture holds if
the positive checkerboard graph of a connected alternating link has
a fixed maximum degree and a sufficiently large number of edges.

% keywords are optional
\bigskip\noindent \textbf{Keywords:} graph; Jones polynomial; real zeros; complex bound
\end{abstract}

\section{Introduction}

Let $T_G(x,y)$ be the Tutte polynomial of the graph $G$
\cite{Tutte}. We shall first give the definition of \emph{the Jones
polynomial} of a graph. Let $G=(V,E)$ be a graph with $k$ components. The Jones
polynomial of $G$ is defined to be
\begin{eqnarray}
J_G(t)=(-1)^{|V|-k}t^{|E|-|V|+k}T_G(-t,-t^{-1}).
\end{eqnarray}


This definition is motivated by the connection between the Jones
polynomial \cite{Jones} of an oriented connected alternating link
and the Tutte polynomial of the positive plane graph formed from an
alternating link diagram of the link via the classical checkerboard
coloring. To be precise, let $L$ be a connected oriented link which
admits an alternating link diagram $D$. Let $V_L(t)$ be the Jones
polynomial of $L$. Let $T_{G_+(D)}$ be the Tutte polynomial of
$G_{+}(D)$, the positive checkerboard graph constructed from $D$.
Then \cite{Th}
\begin{eqnarray}
V_L(t)=(-1)^{w}t^{b-a+3w\over 4}T_{G_+(D)}(-t,-t^{-1}),\label{gk}
\end{eqnarray}
where $w$ is the writhe of the link diagram $D$, $a$ (resp. $b$) is
the number of vertices (resp. regions) of $G_+(D)$.

Zeros of Jones polynomials of links (i.e. plane graphs) have been studied.
In \cite{Wu,Chang,Jab1,Jab2}, some families of links are considered. In \cite{Kof,JZ}, the unit-circle
theorem is obtained. In \cite{JZ1}, the authors proved that zeros of Jones
polynomials of pretzel links are dense in the whole complex plane. There has been a great deal of work on zeros of the chromatic
polynomial (more generally, the Potts model partition function),
which is also a partial evaluation of the Tutte polynomial. See, for
example, \cite{Sokal2} and references therein. In this paper, we try
to use the method of studying (di)chromatic zeros to study zeros of
the Jones polynomial of graphs, hoping to obtain some similar
results.


In the next section we provide some basic properties of the Jones
polynomial of graphs, some of which are specializations of properties of
the Tutte polynomial or generalizations of properties of the Jones
polynomial of alternating links (equivalently, planar graphs). We obtain several results on zeros of the
Jones polynomial of graphs in Section 3. In particular, we prove that $(-\infty, 0]$ is a zero-free
interval of the Jones polynomial of connected bridgeless graphs while
for any small $\epsilon>0$ or large $M>0$, there is a zero of the Jones polynomial
of a plane graph in $(0,\epsilon)$, $(1-\epsilon,1)$, $(1,1+\epsilon)$ or $(M,+\infty)$.

Let $G$ be a connected graph. Let $z_1,z_2,\cdots,z_q$ be all the zeros of $J_G(t)$. Define the Jones spectral radius of $G$ to be

$$
r(G)=\max_{1\leq i\leq q}\{|z_i|\}.
$$
By using Sokal's result \cite{Sokal} and imitating Brown's method
\cite{Br}, we succeed in obtaining an upper bound and a lower bound
for $r(G)$. Let $G=(V,E)$ be a connected bridgeless and loopless
graph of maximum degree $\Delta_G$ with $q_s$ parallel classes. In
Section 4, we prove that
\begin{eqnarray}
{q_s-|V|+1\over |E|}\leq r(G)<1+6.907652\Delta_G.
\end{eqnarray}
As an application of the upper bound, we
discuss a conjecture stated by X.-S. Lin's in \cite{Lin2}, a paper partially written before he passed away in 2007. We conclude the paper in Section 5 with two unsolved problems for further study.


\section{Basic properties}


It is obvious that $J_{E_n}(t)=1$ for the edgeless graph $E_n$ with $n$ vertices and
when a graph contains at least one edge, we have the
following deletion-contraction recurrence which can be used to
compute the Jones polynomial for any graph and thus can
also be viewed as an alternative definition.

\begin{theorem} \label{rec} Let $G=(V,E)$ be a graph and
$e\in E$. Then
\begin{displaymath}
J_G(t)=\left\{
\begin{array}{ll}
tJ_{G/e}(t) & \textrm{if $e$ is a bridge of $G$,}\\
-J_{G-e}(t) & \textrm{if $e$ is a loop of $G$,}\\
tJ_{G-e}(t)-J_{G/e}(t) & \textrm{otherwise,}
\end{array} \right.
\end{displaymath}
where $G-e$ and $G/e$ are graphs obtained from $G$ by deleting and
contracting the edge $e$, respectively. In particular, $J_G(t)$ is a
polynomial with integer coefficients.
\end{theorem}

\begin{proof} The result follows directly from the following
deletion-contraction formula for the Tutte polynomial:
\begin{displaymath} T_G(-t,-t^{-1})=\left\{
\begin{array}{ll}
-t\ T_{G/e}(-t,-t^{-1}) & \textrm{if $e$ is a bridge of $G$,}\\
-t^{-1}\ T_{G-e}(-t,-t^{-1}) & \textrm{if $e$ is a loop of $G$,}\\
T_{G-e}(-t,-t^{-1})+T_{G/e}(-t,-t^{-1}) & \textrm{otherwise.}
\end{array} \right.
\end{displaymath}
See, for example, \cite{B}. 
\end{proof}

\begin{theorem} \label{dua} Let $G$ be a plane graph and
$G^*$ be the planar dual of $G$. Then
\begin{eqnarray}
J_{G^*}(t)=(-t)^{|E|}J_{G}(t^{-1}).
\end{eqnarray}
\end{theorem}

\begin{proof} This follows directly from the following
duality formula for the Tutte polynomial:
\begin{eqnarray*}
T_{G^*}(x,y)=T_G(y,x).
\end{eqnarray*}
See, for example, \cite{B}. 
\end{proof}


\begin{theorem}\label{al}
Let $G=(V,E)$ be a graph. Then the terms in $J_G(t)$
alternate in sign.
\end{theorem}

\begin{proof} Let $K_G(t)=(-1)^{|E|}J_G(-t)$. From Theorem
\ref{rec}, we obtain
\begin{displaymath} K_G(t)=\left\{
\begin{array}{ll}
tK_{G/e}(t) & \textrm{if $e$ is a bridge of $G$,}\\
K_{G-e}(t) & \textrm{if $e$ is a loop of $G$,}\\
tK_{G-e}(t)+K_{G/e}(t) & \textrm{otherwise.}
\end{array} \right.
\end{displaymath}
Now it suffices to show that the coefficients in $K_G(t)$ are all
non-negative. We shall prove this by induction on the number of edges
of $G$. It holds trivially when $G=E_n$. We suppose that it holds
for all graphs with fewer than $m$ edges and let $G$
be a connected graph with $m$ edges. By the above
deletion-contraction formula for $K_G(t)$ and the inductive hypothesis,
it is obvious that the coefficients of $K_G(t)$ are all non-negative.
\end{proof}



\begin{remark} It is possible for some coefficient of $K_G(t)$ to be zero. For
example, $K_{C_n}(t)=t^n+t^{n-1}+\cdots+t^2+1$ for the $n$-cycle
$C_n$ $(n\geq 2)$. Furthermore, it is not difficult for us to derive
from Theorems 14 and 15 in \cite{B} that the coefficients of $K_G(t)$
are all positive for all connected non-separable graphs which are
neither cycles nor dual graphs of cycles.
\end{remark}


Let $G=(V,E)$ be a graph. A \emph{parallel class} of $G$ is a
maximal subset of $E$ all of which have the same endvertices.
A \emph{series class} of $G$ is a maximal subset of $E$ such
that the removal of any two edges of the subset will increase the number of
components of the graph. Both parallel classes and series
classes partition the edge set $E$. In the case of a plane graph, a
parallel class is exactly a series class of its dual graph. A
parallel or series class will be called \emph{trivial} if it
contains only one edge. Let the Tutte polynomial evaluation of the
graph $G$
\begin{eqnarray}\label{1}
T_G(-t,-t^{-1})=a_nt^n+a_{n+1}t^{n+1}+\cdots+a_{m-1}t^{m-1}+a_mt^m,
\end{eqnarray}
with $a_n\neq 0, a_m\neq0$ and $n\leq m$. In \cite{Lin}, Dasbach and
Lin proved:


\begin{lemma}\label{hi}
Let $G=(V,E)$ be a connected loopless graph with $q_s$ parallel
classes and $\tilde{q}_s$ nontrivial parallel classes. Then in
(\ref{1}), $m=|V|-1$ and

\begin{enumerate}
\item[(1)] $a_m=(-1)^{|V|-1}$,
\item[(2)] $a_{m-1}=(-1)^{|V|-1}(|V|-1-q_s)$,
\item[(3)] $a_{m-2}=(-1)^{|V|-1}\left[\left(
\begin{array}{c}
q_s-|V|+2\\
2
\end{array}\right)
+\tilde{q}_s-tri\right],$ where $tri$ is the number of triangles of
the parallel reduction obtained from $G$ by deleting all edges but
one for every parallel class of $G$.
\end{enumerate}
\end{lemma}

\begin{proof} See Proposition 2.1 of \cite{Lin}. By
checking the proof, one finds that the `planarity' condition in
Proposition 2.1 is actually not needed and thus Lemma \ref{hi} follows.
\end{proof}

Now we investigate the value of $n$ and the two coefficients
$a_n$ and $a_{n+1}$ in Eq. (\ref{1}), to obtain a `dual' result of Lemma
\ref{hi}. Let $G=(V,E)$ be a connected bridgeless graph. $S\subset E$ is said
to be a \emph{pairwise-disconnecting set} if $|S|\geq 2$ and the deletion of any two members of $S$ disconnects the graph.. The notion of
pairwise-disconnecting set was introduced in \cite{A}. The following
three statements on pairwise-disconnecting sets are all obvious.


\noindent {\bf ST1:} Any $k$-edge connected graph ($k\geq 3$) does
not contain any pairwise-disconnecting set.

\noindent {\bf ST2:} When $|S|=2$, $S$ is a pairwise-disconnecting
set if and only if $S$ is a 2-edge cut of $G$.

\noindent {\bf ST3:} Any subset with cardinality greater than 1 of a
pairwise-disconnecting set $S$ is also a pairwise-disconnecting set.


\begin{proposition}\label{111}
Let $G=(V,E)$ be a connected bridgeless graph, $S\subset E$ and
$|S|\geq 2$. Then the following are equivalent:
\begin{itemize}
\item $S$ is a pairwise-disconnecting set.
\item $S=\{e_1,e_2,\cdots,e_k\}$ is a set of edges in a cycle such that $G-S=G_1\cup
G_2\cup\cdots\cup G_k$ and each $G_i$ ($i=1,2,\cdots,k$) is
connected, as shown in Fig. \ref{cyc}.
\item $k(G-S)=|S|$.
\end{itemize}
\end{proposition}

\begin{figure}[htbp]
\centering
\includegraphics[width=6.5cm]{cycle.eps}
\renewcommand{\figurename}{Fig.}
\caption{$S=\{e_1,e_2,\cdots,e_k\}$ and $G-S=G_1\cup
G_2\cup\cdots\cup G_k$ and each $G_i$ ($i=1,2,\cdots,k$) is
connected.}\label{cyc}
\end{figure}

\begin{proof} We first prove that if $k(G-S)=|S|$, then all
edges of $S$ occur on a cycle of $G$ as shown in Fig. \ref{cyc}. It
holds when $|S|=2$ and now we suppose $|S|\geq 3$ and $f\in S$. Because
$k(G-S)=|S|$ we have $k(G-S+f)=|S-f|$ and $f$ is a bridge of
$G-S+f$. By the inductive hypothesis the edges $S-f$ occur on a cycle of
$G$. Suppose that $G$ becomes $G_1,G_2,\cdots,G_{|S-f|}$ when $S-f$ is
deleted. Then $f$ belongs to some $G_i$ and is also a bridge of
$G_i$. Hence, all edges of $S$ occur on a cycle of $G$.

It is clear that if all edges of $S$ occur on a cycle of $G$ as shown
in Fig. \ref{cyc}, then $S$ is a pairwise-disconnecting set.

Finally we prove that if $S$ is pairwise-disconnecting set, then
$k(G-S)=|S|$. It holds when $|S|=2$ and now we suppose $|S|\geq 3$
and $f\in S$. Then $S-f$ is also a pairwise-disconnecting set. By
the inductive hypothesis we have $k(G-S+f)=|S-f|$. Let $g\in S-f$. Then
$\{f,g\}$ is a 2-edge cut of $G$. Hence, $f$ is a bridge of $G-g$
and also a bridge of $G-S+f$. Therefore, we have
$k(G-S)=k(G-S+f)+1=|S-f|+1=|S|$. \end{proof}




A pairwise-disconnecting set $S_M$ is said to be \emph{maximal} if
no pairwise-disconnecting set contains it as a proper subset. Note that maximal pairwise-disconnecting sets are exactly nontrivial maximal series classes.

\begin{proposition}\label{222}
Let $G$ be a connected bridgeless graph. For any given
pairwise-disconnecting set $S$ of $G$, there exists a unique maximal
pairwise-disconnecting set $S_M$ of $G$ containing~$S$.
\end{proposition}

\begin{proof} The existence follows from the definition of
pairwise-disconnecting sets directly. To prove the uniqueness, we
suppose that there are two distinct maximal pairwise-disconnecting
sets $S_M^1$ and $S_M^2$ of $G$ such that $S\subset S_M^i$
($i=1,2$). Let $e,f\in S$ and $g\in S_M^2-S_M^1$. Then $\{e,f\}$ is
a 2-edge cut of $G$. Suppose that $G-e-f=G_1\cup G_2$. Without
loss of generality we suppose that $g\in E(G_2)$. Since $e,f,g\in
S_M^2$, $\{e,g\}$ is a 2-edge cut of $G$, which
implies that $g$ must be a bridge of $G_2$. We suppose that
$G_2-g=G_2'\cup G_2''$. See Fig. \ref{uni} (a). Let $h\in
S_M^1-e-f$. We shall show that $\{h,g\}$ is a 2-edge cut of $G$.
Since $e,f,h\in S_M^1$, $\{e,h\}$ is a 2-edge cut of
$G$, which implies that $h$ must be a bridge of $G_1$ or $G_2$.
There are two cases.

\noindent {\bf Case 1.} $h$ is a bridge of $G_1$. Suppose that
$G_1-h=G_1'\cup G_1''$, then $G-g-h$ is disconnected as shown in
Fig. \ref{uni} (b).

\noindent {\bf Case 2.} $h$ is a bridge of $G_2$. Without loss of
generality, we suppose that $h\in G_2'$, then $h$ is also a bridge
of $G_2'$. Suppose that $G_2'-h=G_{21}'\cup G_{22}'$, then $G-g-h$
is also disconnected as shown in Fig. \ref{uni} (c).

\noindent Hence, $S_M^1\cup \{g\}$ is a pairwise-disconnecting set,
which contradicts the maximality of $S_M^1$. \end{proof}

\begin{figure}[htbp]
\centering
\includegraphics[width=9.5cm]{unique.eps}
\renewcommand{\figurename}{Fig.}
\caption{The proof of Proposition \ref{222}.}\label{uni}
\end{figure}

\begin{lemma}\label{lo}
Let $G=(V,E)$ be a connected bridgeless graph with $q_r$ series
classes. Then in (\ref{1}), $n=-|E|+|V|-1$ and
\begin{enumerate}
\item[(1)] $a_n=(-1)^{|E|-|V|+1}$,
\item[(2)] $a_{n+1}=(-1)^{|E|-|V|+1}(-|V|+1+|E|-q_r)$.
\end{enumerate}
\end{lemma}

\begin{proof} Recall that
\begin{eqnarray*}
T_G(-t,-t^{-1})&=&\sum_{F\subseteq
E}(-t-1)^{k(F)-1}(-t^{-1}-1)^{|F|-|V|+k(F)}\\
&=&\sum_{F\subseteq
E}(-1)^{|F|-|V|+1}(1+t)^{k(F)-1}(t^{-1}+1)^{|F|-|V|+k(F)}.
\end{eqnarray*}
It is clear that $k(F)-1\geq 0$. Thus we obtain
\begin{eqnarray*}
(1+t)^{k(F)-1}=1+(k(F)-1)t+\left(
\begin{array}{c}
k(F)-1\\
2
\end{array}
\right)t^2+\cdots.
\end{eqnarray*}
Since $|F|-|V|+k(F)$ is the nullity of the subgraph $(V,F)$ of
$G=(V,E)$, $0\leq|F|-|V|+k(F)\leq |E|-|V|+1$. Now
\begin{eqnarray*}
(t^{-1}+1)^{|F|-|V|+k(F)}&=&t^{-({|F|-|V|+k(F)})}+({|F|-|V|+k(F)})t^{-(|F|-|V|+k(F)-1)}\\
&+& \left(
\begin{array}{c}
|F|-|V|+k(F)\\
2
\end{array}
\right)t^{-(|F|-|V|+k(F)-2)}+\cdots.
\end{eqnarray*}

Note that $G$ is connected and bridgeless, so
$|F|-|V|+k(F)=|E|-|V|+1$ if and only if $F=E$. Hence,
$n=-|E|+|V|-1$ and $a_n=(-1)^{|E|-|V|+1}$. Furthermore,
$|F|-|V|+k(F)=|E|-|V|$ if and only if $F=E-e$ for $e\in E$ or, by
Proposition \ref{111} $F=E-S$, where $S$ is a pairwise-disconnecting
set of $G$. Thus,

\begin{eqnarray*}
a_{n+1}&=&(-1)^{|E|-|V|+1}(|E|-|V|+1)+(-1)^{|E|-|V|}|E|+
\sum_{E-S}(-1)^{|E-S|-|V|+1}\\
&=&(-1)^{|E|-|V|+1}(-|V|+1)+\sum_{E-S_M}\sum_{S\subset S_M}(-1)^{|E-S|-|V|+1}\\
& & \textrm{(By Proposition \ref{222})}\\
&=&(-1)^{|E|-|V|+1}(-|V|+1+\sum_{S_M}(|S_M|-1))\\
&=&(-1)^{|E|-|V|+1}(-|V|+1+|E|-q_r).
\end{eqnarray*}

\end{proof}


\begin{theorem}\label{ddd} Let $G=(V,E)$ be a connected bridgeless and loopless
graph. Then, with notation as above,
\begin{eqnarray}\label{ssss}
J_G(t)=b_0+b_1t+b_2t^2+\cdots+b_{|E|-2}t^{|E|-2}+b_{|E|-1}t^{|E|-1}+b_{|E|}t^{|E|},
\end{eqnarray}
where $(-1)^{|E|-i}b_i$ is a non-negative integer for $i=0,1,2,\cdots,|E|$ and in particular,
\begin{eqnarray*}
b_0&=&(-1)^{|E|},\\
b_1&=&(-1)^{|E|}(-|V|+1+|E|-q_r),\\
b_{|E|-2}&=&\left(
\begin{array}{c}
q_s-|V|+2\\
2
\end{array}\right)
+\tilde{q}_s-tri,\\
b_{|E|-1}&=&|V|-1-q_s,\\
b_{|E|}&=&1.
\end{eqnarray*}
\end{theorem}

\begin{proof} This follows from Theorems \ref{rec} and \ref{al}, and Lemmas \ref{hi} and \ref{lo}.
\end{proof}



\begin{lemma}\label{com2}
Let $G$ be a connected plane graph. Then
\begin{eqnarray}
J_G(1)=(-1)^{|E|-|V|+1}(-2)^{\mu(G)-1},
\end{eqnarray}
where $\mu(G)$ is the number of left-right paths of $G$ (or equivalently,
the number of crossing circuits of the medial graph $M(G)$ of $G$ and the number of components of the link represented by $D(G)$).
\end{lemma}

Lemma \ref{com2} follows from results by Martin \cite{Mar} and Las Vergnas \cite{Las}, see also \cite{welsh}. In fact, $\mu(G)-1$ is exactly the dimension of the bicycle space of $G$ \cite{RR,SH}.

\section{Real and non-real zeros}

Let $G$ be a connected bridgeless and loopless graph with $p$ vertices, $q$ edges, and $q_s$ parallel classes. Let $z_k=x_k+i y_k$ ($k= 1,2,\cdots, q$) be zeros of $J_G(t)$ of the graph $G$. Then, according to Theorem \ref{ddd}, we have
\begin{enumerate}
\item[(1)] $J_G(t)=\prod_{k=1}^q(t-z_k)$.
\item[(2)] Let $\sum_{+} z_k$ (resp. $\sum_{-} z_k$) indicates the sum of those $z_k$, $k=1,2,\cdots,q$ whose real parts are positive (resp. negative). Then $\sum_{+} z_k$ (resp. $\sum_{-} z_k$) is a positive (resp. negative) real number.
\item[(3)] $\sum z_k=q_s-p+1\geq 0$.
\item[(4)] $\prod_{k=1}^q z_k=1.$
\end{enumerate}

Now we start to discuss the real and non-real zeros of the Jones polynomial of a graph.

\begin{theorem}\label{rea} Let $G$ be a connected bridgeless and loopless graph. Then
\begin{enumerate}
\item[(1)] $J_G(t)$ has no negative real zeros.
\item[(2)] $J_G(t)$ has no rational zeros.
\end{enumerate}
\end{theorem}

\begin{proof} Theorem \ref{rea} (1) follows directly from
Theorem \ref{al}. Note that the extreme coefficients of $J_G(t)$ are
both $\pm 1$, so by the Rational Root Theorem, only $\pm 1$'s may be
possible rational roots. However $1$ is not a zero by Lemma \ref{com2} and $-1$ is not a zero either by Theorem \ref{rea}
(1). Thus Theorem \ref{rea} (2) holds. \end{proof}

\begin{remark}
The results in Theorem \ref{rea} on zeros of the Jones polynomial of knots and links, i.e. the case of the Jones polynomial of a planar graph have been obtained previously. See Theorem 3.1 in \cite{Tao}.
\end{remark}

\begin{corollary}\label{rea2}
Let $G$ be a connected bridgeless and loopless graph. If the number of edges of $G$ is odd, then $J_G(t)$ has a (positive and irrational) real zero.
\end{corollary}


It is natural to look for a small positive $\epsilon$ such that any $z\in (0,\epsilon)$ is not a zero of the Jones polynomials of a graph. In the following we shall show such an $\epsilon$ does not exist.

Let $G_n$ be the 3-regular planar graph shown in the upper part of Fig. \ref{gnn1}. It is called the Gustin current graph, see \cite{GT}.
Note that $G_n$ has $2n+2$ vertices and $3n+3$ edges.
We will show that for any $\epsilon>0$,
there exists an integer $n$ such that $J_{G_n}(t)$ has a root
in $(0,\epsilon)$.

\begin{figure}[htbp]
\centering
\includegraphics[width=10cm]{gn.eps}
\renewcommand{\figurename}{Fig. }
\caption{The graph $G_n$ (upper) and the graph $H_n$ (down)}.\label{gnn1}
\end{figure}


Let $N_G(t)=(-1)^{|E|}J_G(t)=(-1)^{|E|+|V|-1}t^{|E|-|V|+1}T_G(-t,-t^{-1})$.
Then $N_G(t)$ can be obtained using the following recurrence relations:
$$
N_G(t)=
\left \{
\begin{array}{ll}
1, &\mbox{if }G=K_1;\\
-tN_{G/e}(t), &\mbox{if }e\mbox{ is a bridge of }G;\\
N_{G-e}(t), &\mbox{if }e\mbox{ is a loop of }G;\\
-tN_{G-e}(t)+N_{G/e}(t), &\mbox{if }e\mbox{ is not a bridge nor a loop of }G.
\end{array}
\right.
$$
Note that if $G$ is bridgeless,
$N_G(t)$ is a polynomial with constant term equal to $1$,
i.e., $N_G(0)=1$.
Using this property, we see that $N_G(t)$ has a root in
$(0,a)$ if $N_G(a)<0$, and $a>0$.

Now we want to find an expression for $N_{G_n}(t)$.
For this purpose, we need to make use of another two graphs $H_n$ and
$Q_n$.
Let $H_n$ be the graph, shown in lower part of Fig. \ref{gnn1},
obtained from $G_n$ by deleting the vertex $v_{2n+2}$
and $Q_n$ be the graph obtained from $H_n$
by adding an edge parallel to the edge joining $v_{2n-1}$ and $v_{2n}$.


\begin{lemma}\quad \label{le-01}
$$
N_{H_{1}}(t)=1+t^2-t^3,
$$
$$
N_{H_{2}}(t)=1-t+t^2-t^3+t^4+t^2(1-t)N_{H_{1}}(t),
$$
and for $n\ge 3$, we have
\begin{eqnarray}\label{HHH}
N_{H_{n}}(t)=(1-t)(1+t^2) N_{H_{n-1}}(t)+t^3N_{H_{n-2}}(t).
\end{eqnarray}
\end{lemma}

\begin{proof} For convenience let $h_n=N_{H_{n}}(t)$ and $q_n=N_{Q_{n}}(t)$. Note that $H_1$ is actually $K_3$ and so we have
$h_1=1+t^2-t^3$.
When $n\ge 2$, we have
$$
h_n=(t^2-t^3)h_{n-1}+q_{n-1}
$$
and
$$
q_n=t^2h_{n-1}-th_n+q_{n-1}.
$$
It is easy to check that
$q_1=1-t+t^2-t^3+t^4$. Thus
$h_2=1-t+t^2-t^3+t^4+t^2(1-t)h_1$.
For $n\ge 2$, we have
\begin{eqnarray*}
h_{n+1}-h_n
&=&t^2(1-t)(h_n-h_{n-1})+(q_n-q_{n-1})\\
&=&t^2(1-t)(h_n-h_{n-1})+t^2h_{n-1}-th_n,
\end{eqnarray*}
implying that
\[
h_{n+1}=(1-t)(1+t^2)h_n+t^3h_{n-1}.
\qedhere\]
\end{proof}

\begin{lemma}\quad \label{le-02}
For $n\ge 3$,
$$
N_{G_n}(t)=(1-t)^2N_{G_{n-1}}(t)-t^2N_{G_{n-2}}(t)
-t^3N_{H_n}(t)-t^5N_{H_{n-1}}(t).
$$
\end{lemma}

\begin{proof} We write $g_n$ for $N_{G_n}(t)$.
For $i=1,2$, let $e_i$ be the edge joining vertices $v_{2n+2}$ and $v_{2n-2+i}$. Then for $n\ge 2$,
$$
g_n=N_{G_n/e_1/e_2}(t)-tN_{(G_n-e_1)/e_2}(t)
-tN_{(G_n/e_1)-e_2}(t)
+t^2N_{G_n-e_1-e_2}(t).
$$
Note that $N_{G_n/e_1/e_2}(t)=g_{n-1}$,
$N_{G_n-e_1-e_2}(t)=-tN_{H_n}(t)$ and
$N_{(G_n-e_1)/e_2}(t)=N_{(G_n/e_1)-e_2}(t)=N_{T_n}(t)$,
where $T_n$ is the graph obtained from $H_n$ by adding
an edge joining $v_{2n}$ and $v_{2n+1}$.
Thus
$$
g_n=g_{n-1}-2tN_{T_n}(t)-t^3h_n.
$$
For $n\ge 2$, we also have
\begin{eqnarray*}
N_{T_n}(t)&=&N_{T_n/e_3}(t)-tN_{T_n-e_3}(t)\\
&=&g_{n-1}+t^2N_{(T_n-e_3)/e_4}(t)\\
&=&g_{n-1}+t^2(N_{T_{n-1}}(t)+t^2h_{n-1}),
\end{eqnarray*}
implying that $N_{T_n}(t)-t^2N_{T_{n-1}}(t)=g_{n-1}+t^4h_{n-1}$, where $e_3$ is the edge joining $v_{2n-1}$ and $v_{2n}$
and $e_4$ is the edge joining $v_{2n-1}$ and $v_{2n-3}$.
Hence, for $n\ge 2$, we have
\begin{eqnarray*}
g_{n+1}-t^2g_n&=&g_{n}-2tN_{T_{n+1}}(t)-t^3h_{n+1}
-t^2(g_{n-1}-2tN_{T_n}(t)-t^3h_n)\\
&=&g_{n}-t^3h_{n+1}-t^2(g_{n-1}-t^3h_n)
-2t(N_{T_{n+1}}(t)-t^2N_{T_{n}}(t))\\
&=&g_{n}-t^3h_{n+1}-t^2(g_{n-1}-t^3h_n)
-2t(g_{n}+t^4h_{n}),
\end{eqnarray*}
implying that
\[
g_{n+1}=(1-t)^2g_n-t^2g_{n-1}-t^3h_{n+1}-t^5h_n.
\qedhere\]
\end{proof}


Lemma~\ref{le-01} implies that
$N_{H_n}(t)>0$ for all $n\ge 1$ when $t\in (0,1)$.
So, by Lemma~\ref{le-01},  for all $n\ge 3$,
$$
N_{H_n}(t)> (1-t)N_{H_{n-1}}(t),
$$
implying that
$$
N_{H_n}(t)> (1-t)^{n-2}N_{H_2}(t)
$$
and of course
$$
N_{H_n}(t)+t^2N_{H_{n-1}}(t)
> (1-t)^{n-2}N_{H_2}(t).
$$

\begin{lemma} \label{le1}
For any $t\in (0,1)$, there exists $m$ such that $N_{G_m}(t)<0$.
\end{lemma}

\begin{proof}
Let $t\in (0,1)$ be fixed.
Suppose that the result fails.
Thus $g_n\ge 0$ for all $n$.
Then, by Lemma~\ref{le-02}, for all $n\ge 3$,
$$
g_n\le (1-t)^2g_{n-1}-t^3h_n-t^5h_{n-1}
$$
$$
\le (1-t)^2g_{n-1}
-t^3(1-t)^{n-2}h_{2},
$$
implying that
\begin{eqnarray*}
g_n&\le & (1-t)^{2(n-2)}g_{2}-t^3h_{2}
\sum_{i=1}^{n-2}(1-t)^{2(n-2-i)}(1-t)^{i}\\
&=&(1-t)^{2(n-2)}g_{2}-t^3(1-t)^{n-2}h_{2}
\sum_{i=1}^{n-2}(1-t)^{n-2-i}\\
&=&(1-t)^{2(n-2)}g_{2}-t^2(1-t)^{n-2}h_{2}(1-(1-t)^{n-2})\\
&=&(1-t)^{n-2}\left ((1-t)^{n-2}(g_{2}+t^2h_2)-t^2h_2\right ),
\end{eqnarray*}
where the last expression will be negative
when $n$ is sufficiently large
because $t^2h_2>0$, a contradiction.
\end{proof}

\begin{theorem}
For any $0<\epsilon<1$, there is an integer $m>0$ such that
$N_{G_m}(t)$
has a zero in $(0,\epsilon)$.
\end{theorem}

\begin{proof}
Note that $N_{G_n}(0)=1$ for all $n\ge 1$. By Lemma \ref{le1}, there is an integer $m$ such that
$N_{G_m}(\epsilon)<0$.
Thus the polynomial $N_{G_m}(t)$ has a zero in $(0,\epsilon)$.
\end{proof}


In Lemma \ref{le-01}, if we assume the linearly recursive relation (\ref{HHH}) holds for $n=2$,
then $N_{H_0}(t)=1$. The characteristic equation of the
linearly recursive relation (\ref{HHH}) is
\begin{eqnarray*}
x^2-(1-t)(1+t^2)x -t^3=0.
\end{eqnarray*}
For any fixed real $t>1$, it has two non-equal solutions
$L_1$ and $L_2$:
\begin{eqnarray*}
L_1(t)&=&{1\over 2}[(1-t)(t^2+1)+
\sqrt{t^6-2t^5+3t^4+3t^2-2t+1}]\\
L_2(t)&=&{1\over 2}[(1-t)(t^2+1)-
\sqrt{t^6-2t^5+3t^4+3t^2-2t+1}].
\end{eqnarray*}
Thus, there exist $A(t)$ and $B(t)$ such that
for all $n\ge 0$,
\begin{eqnarray*}
N_{H_n}(t)=A(t)[L_1(t)]^n+B(t)[L_2(t)]^n.
\end{eqnarray*}
By the given condition on $N_{H_0}(t)$ and $N_{H_1}(t)$, it is easy to find $A(t)$ and $B(t)$:
$$
A(t)=\frac{1+t^2-t^3-L_2(t)}{L_1(t)-L_2(t)}; \quad
B(t)=-\frac{1+t^2-t^3-L_1(t)}{L_1(t)-L_2(t)}.
$$

Now we claim:

\textit{For any real $t>1$, $A(t)>0$, $B(t)>0$, $L_1(t)>0$ and $L_2(t)<0$.}

The above claim is shown. As an example, we show that $B(t)>0$.
It is clear that $L_1(t)-L_2(t)>0$ for $t>1$. So $B(t)>0$ if and only if $L_1(t)-(1+t^2-t^3)>0$.
Observe that
$$
L_1(t)-(1+t^2-t^3)=\frac 12 \left (t^3-t^2-t-1+\sqrt{t^6-2t^5+3t^4+3t^2-2t+1}\right )
$$
and
\begin{eqnarray*}
& &t^3-t^2-t-1+\sqrt{t^6-2t^5+3t^4+3t^2-2t+1}\\
&=&(t-1)^2(t+1)-2+\sqrt{t^6-2t^5+3t^4+3t^2-2t+1}\\
&=&(t-1)^2(t+1)-2+\sqrt{4+(t-1)(t^5-t^4+2t^3+2t^2+5t+3)}\\
&>&(t-1)^2(t+1)-2+\sqrt 4\\
&>&0
\end{eqnarray*}
for $t>1$.


Since $L_1(t)+L_2(t)=(1-t)(1+t^2)<0, L_1(t)>0$ and $L_2(t)<0$ for $t>1$, we have $\frac {L_2(t)}{L_1(t)}<-1$. Hence, for any fixed $t>1$,
\begin{eqnarray*}
N_{H_n}(t)&=&A(t)[L_1(t)]^n+B(t)[L_2(t)]^n\\
&=&
[L_1(t)]^n\left[A(t)+B(t)\left (\frac {L_2(t)}{L_1(t)}\right )^n\right]\\
&<& 0
\end{eqnarray*}
for all sufficiently large odd $n$. In addition, by Lemma \ref{le-01}, it is easy to prove $N_{H_n}(1)=1$ for all $n\geq 0$. Thus,

\begin{theorem}
For any $\epsilon>0$, there exists an integer $m$ such that
for all odd $n\ge m$, $N_{H_n}(t)$ has a real zero in $(1,1+\epsilon)$.
\end{theorem}

\begin{remark}
By Theorem \ref{dua}, for any small $\epsilon$, there is a real zero of a Jones polynomial in $(1-\epsilon,1)$ and for any large $M>0$, there is a real zero in $(M,+\infty)$.
\end{remark}

Now we consider non-real zeros of Jones polynomials.


\begin{theorem}\label{com} Let $G$ be a connected bridgeless and loopless nontrivial
graph with notations above. If
$$tri<\left(
\begin{array}{c}
q_s-p+2\\
2
\end{array}\right)
+\tilde{q}_s-{q-1\over 2q}(p-1-q_s)^2,$$ then $J_G(t)$ has a
non-real zero.
\end{theorem}

\begin{proof} Theorem \ref{com} follows from the following
theorem (see \cite{Har}): let
$f(x)=\sum_{k=0}^na_kx^{k}=a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\cdots+a_{1}x+a_0$
be a polynomial of degree $n\geq 2$ with real coefficients, a
necessary condition for all zeros of $f(x)$ to be real is ${k\over
n-k+1}{n-k\over k+1}a_k^2-a_{k-1}a_{k+1}\geq 0$ for each
$k=1,2,\cdots,n-1$. Taking $k=n-1$, if ${n-1\over
2n}a_{n-1}^2-a_na_{n-2}<0$ which is equivalent to the condition in
Theorem \ref{com} for $J_G(t)$ via Theorem \ref{ddd}, then $J_G(t)$
has a non-real zero. \end{proof}

\begin{corollary}\label{sp} Let $G$ be a connected bridgeless simple
triangle-free non-trivial graph. Then $J_G(t)$ has a non-real zero.
\end{corollary}

\begin{proof} In this case the parallel reduction of $G$ is
itself, $q_s=q$ and $\tilde{q}_s=0$. Note that $c(G)=q-p+1>0$ since
$G$ is bridgeless and non-trivial. Thus,
\begin{eqnarray*}& &\left(
\begin{array}{c}
q_s-p+2\\
2
\end{array}\right)
+\tilde{q}_s-{q-1\over 2q}(p-1-q_s)^2\\
&=&\left(
\begin{array}{c}
c(G)+1\\
2
\end{array}\right)
-{q-1\over 2q}c^2(G)\\
&=&{1\over 2q}c^2(G)+{c(G)\over 2}\\
&>&0.
\end{eqnarray*}
By Theorem \ref{com}, Corollary \ref{sp} holds. \end{proof}



\section{Complex bounds}


In this section, we consider lower and upper bounds for $r(G)$.

\begin{theorem} Let $G$ be a connected bridgeless and loopless graph
with $p$ vertices, $q$ edges, $q_s$ parallel classes and
$\tilde{q}_s$ nontrivial parallel classes. Let
$\Delta=(q-1)^2(q_s-p+1)^2-2q(q-1)\left[\left(
\begin{array}{c}
q_s-p+2\\
2
\end{array}\right)
+\tilde{q}_s-tri\right],$ where $tri$ is the number of triangles of
the parallel reduction of $G$. Then
\begin{enumerate}
\item[(1)] $J_G(t)$ has a root $z$ whose real part is at least
${q_s-p+1\over q}+{\sqrt{\Delta}\over q(q-1)}$ if $\Delta\geq 0$;
\item[(2)] $J_G(t)$ has two (not necessarily distinct) roots $z_1$ and $z_2$ such that the real part of
$z_1$ is at least ${q_s-p+1\over q}$ and the imaginary part of $z_2$
is at least ${\sqrt{-\Delta}\over q(q-1)}$ if $\Delta<0$.
\end{enumerate}
\end{theorem}

\begin{proof} Note that in (\ref{ssss}),
$b_q=1$,$b_{q-1}=(p-1-q_s)$ and $b_{q-2}=\left(
\begin{array}{c}
q_s-p+2\\
2
\end{array}\right)
+\tilde{q}_s-tri$. Consider the $(q-2)th$ derivative of $J_G(t)$. We
obtain
$$
{1\over(q-2)!}J^{(q-2)}_G(t)={q(q-1)\over
2}t^2-(q-1)(q_s-p+1)t+b_{q-2}.
$$
Then ${q_s-p+1\over q}+{\sqrt{\Delta}\over q(q-1)}$ is one of the
roots of the above quadratic. Lucas's theorem states that if $f$ is a nonconstant polynomial, then the roots of
the derivative $f'$ lie in the convex hull of the roots of
$f$. It follows that the theorem holds. \end{proof}



As a direct consequence, we have:

\begin{corollary} Let $G=(V,E)$ be a connected bridgeless and loopless graph with
$q_s$ parallel classes. Then
\begin{eqnarray}
r(G)\geq{q_s-|V|+1\over |E|}.
\end{eqnarray}
\end{corollary}

Finally we try to find an upper bound. Let $G=(V,E)$ be a graph.
Assign to each edge $e\in E$ a complex weight $v_e$. Let
$Z_G(q,\{v_e\})$ be the Potts model partition function, i.e.
\begin{eqnarray}
Z_G(q,\{v_e\})=\sum_{F\subset E}q^{k(F)}\prod_{e\in F}v_e,
\end{eqnarray}
where the summation is over all subsets of $E$, and $k(F)$ is the
number of components of the spanning subgraph of $G$ with edge set
$F$.

In \cite{Sokal}, Sokal proved the following important result
(Corollary 5.2) on zeros of the Potts model partition function:

\begin{theorem}\label{s}
Let $G=(V,E)$ be a loopless graph of maximum degree $\leq r$,
equipped with complex edge weights $\{v_e\}_{e\in E}$ satisfying
$|1+v_e|\leq 1$ for all $e$. Let $v_{\max}=\max_{e\in E}|v_e|$. Then
all the zeros of $Z_G(q,\{v_e\})$ lie in the disc
$|q|<C(r)v_{\max}$, where $C(r)<Kr$ with $K\leq 7.963907$.
\end{theorem}

\begin{remark}\label{rs}
In \cite{Sokal1}, the upper bound of the value of $K$ has been
improved to approximately 6.907652.
\end{remark}

\begin{lemma}\label{2}
Let $G=(V,E)$ be a connected graph. Then
\begin{eqnarray}
J_G(t)=t^{|E|+1}(1+t)^{-|V|-1}Z_G(t+2+t^{-1},-t^{-1}-1).
\end{eqnarray}
\end{lemma}

\begin{proof} From the rank-generating form of the Tutte
polynomial \cite{B}, we obtain
\begin{eqnarray*}
J_G(t)&=&(-1)^{|V|-1}t^{|E|-|V|+1}\sum_{F\subset
E}(-t-1)^{k(F)-1}(-t^{-1}-1)^{|F|-|V|+k(F)}\\
&=&t^{|E|-|V|+1}(1+t)^{-1}\sum_{F\subset
E}(-1)^{|F|}(t+1)^{k(F)}(t^{-1}+1)^{|F|-|V|+k(F)}\\
&=&t^{|E|-|V|+1}(t+1)^{-1}\sum_{F\subset
E}(-1)^{|F|}(t+2+t^{-1})^{k(F)}(t^{-1}+1)^{|F|-|V|}\\
&=&t^{|E|-|V|+1}(t+1)^{-1}(t^{-1}+1)^{-|V|}\sum_{F\subset
E}(t+2+t^{-1})^{k(F)}(-t^{-1}-1)^{|F|}\\
&=&t^{|E|+1}(1+t)^{-|V|-1}Z_G(t+2+t^{-1},-t^{-1}-1).
\end{eqnarray*}
\end{proof}




\begin{theorem}
Let $G=(V,E)$ be a connected bridgeless and loopless graph of
maximum degree $\Delta_G$. Let $z$ be any complex zero of $J_G(t)$.
Then $|z+1|<6.907652\Delta_G$.
\end{theorem}

\begin{proof} By Lemma \ref{2}, it suffices to show that any
zero $z$ of $Z_G(t+2+t^{-1},-t^{-1}-1)$ satisfies
$|z+1|<6.907652\Delta_G$. Let $z$ be any fixed zero of
$Z_G(t+2+t^{-1},-t^{-1}-1)$. Note that $\Delta_G\geq 2$, hence if
$|z|\leq 1$, it is clear that $|z+1|<6.907652\Delta_G$. Now we
suppose that $|z|>1$. Note that $|z|>1$ implies that $|-z^{-1}|\leq
1$. By Theorem \ref{s} and the following Remark \ref{rs}, we have
$|z+2+z^{-1}|<6.907652\Delta_G |-z^{-1}-1|$, which implies
$|z+1|<6.907652\Delta_G$. \end{proof}



\begin{corollary} \label{ub} Let $G$ be a connected bridgeless and loopless
graph of maximum degree $\Delta_G$. Then
\begin{eqnarray}
r(G)<1+6.907652\Delta_G.
\end{eqnarray}
\end{corollary}



We have mentioned in the introduction that if we restrict $J_G(t)$
to connected plane graphs, we obtain the Jones polynomial of the
corresponding alternating links up to a factor $\pm t^k$ for some
$k$. See Eq. (\ref{gk}). In this case Theorem \ref{rea} will reduce
to a (partial) result of Theorem 3.1 in \cite{Tao}.


Let $L$ be a connected reduced (equivalently, the corresponding
checkerboard graph is bridgeless and loopless) alternating link with
$N$ crossings, $\lambda_1$,$\lambda_2$,$\cdots$,$\lambda_N$ be zeros
of $V_L(t)$ (treated as a polynomial in the common sense such that
$V_L(0)\neq 0$) and let $\parallel
L\parallel=|\lambda_1|+|\lambda_2|+\cdots+|\lambda_N|$. In
\cite{Lin2}, X.-S. Lin claimed that $\parallel L\parallel\geq N$ and
posed the following conjecture:
\begin{conjecture}
$\parallel L\parallel$ has an upper bound in the order of
$N^{1+\epsilon}$.
\end{conjecture}

Some experimental data on some families of alternating links in
favor of the conjecture have been given by X.-S. Lin himself in
\cite{Lin2} and the conjecture also holds for an alternating link
whose positive checkerboard graph can be obtained from a connected
plane graph by subdividing some of its edges uniformly and the times
of subdivision are large enough \cite{JZ}. Now we apply Corollary
\ref{ub} to provide more evidence for the conjecture.

Suppose that $L$ is a connected reduced link diagram and its
corresponding positive checkerboard graph is $G$ which is connected,
bridgeless and loopless. Note that the number $N$ of crossings of
$L$ is exactly the number of edges of $G$. Then

\begin{corollary}
For any fixed $\epsilon>0$, if $N=|E(G)|>(1+7\Delta_G)^{1\over
\epsilon}$, then $\parallel L\parallel<N^{1+\epsilon}.$
\end{corollary}


A connected plane graph with a fixed maximum degree and edge number
large enough exists widely. For example, the dual of a triangulation
(i.e. maximal planar graph) is 3-regular and the number of its edges
can be large enough, the cylindrical square lattice $P_m\times C_n$
whose maximum degree is 4 and edge number is $(2m-1)n$.  In the case
of $P_{n+1\over 2}\times C_{n}$, it corresponds exactly to the
`weaving' knot $J_n$ in \cite{Lin2}.

\section{Concluding remarks}

It is
known (see \cite{Jack,Thom}) that no graph has a root of its chromatic polyno-
mial in $(-\infty,0)\cup (0,1)\cup (1,32/27]$, and that for any $\lambda\ge 32/27$, there is
a graph whose chromatic polynomial has a real root arbitrary close to $\lambda$. It is natural to pose the following problem for further consideration.

\begin{open}
Characterize other zero-free intervals of Jones polynomials of connected bridgeless and loopless graphs in the real axis or prove that real zeros of Jones polynomials of connected bridgeless and loopless graphs are dense in the positive real axis.
\end{open}


\begin{open}
Does there exist a connected bridgeless and loopless graph $G$ such that all the zeros of $J_G(t)$ are real?
\end{open}
By now, we have not found a connected bridgeless and loopless graph for which all the zeros of the Jones polynomial are real.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
 We thank Profs. Fuji Zhang and Yichao Chen for some helpful discussions.



\begin{thebibliography}{10}

\bibitem{A} T. Albertson. \newblock The twist numbers of graphs and the Tutte
polynomial. See \url{http://www.math.csusb.edu/reu/ta05.pdf}

\bibitem{B} B. Bollob\'as. \newblock{\em Modern Graph Theory}. \newblock Springer, Berlin, 1998.

\bibitem{Br} J.~I. Brown. \newblock On the roots of chromatic polynomials. \newblock {\em J.
Combin. Theory Ser. B}, 72(2):251--256, 1998.

\bibitem{Kof} A. Champanerkar and L. Kofman. \newblock On the Mahler measure of Jones polynomials
under twisting. \newblock {\em Algebr. Geom. Topol.}, 5:1--22, 2005.

\bibitem{Chang} S.-C. Chang and R. Shrock.\newblock Zeros of Jones polynomials for families of knots
and links.\newblock {\em Physica A}, 301:196--218, 2001.


\bibitem{Lin} O. Dasbach and X.-S. Lin. \newblock A volumish theorem for the
Jones polynomial of alternating knots.\newblock {\em Pacific J. Math.}, 231:279--291, 2007.

\bibitem{GT} J.~L. Gross and T.~W. Tucker. \newblock {\em Topological Graph Theory}. \newblock John Wiley \& Sons, 1987.

\bibitem{Har} G.~H. Hardy, J.~E. Littlewood, and G. Poly\'a.
\newblock {\em Inequalitites}. \newblock Cambridge University Press, Cambridge, 1952.

\bibitem{Jab1} S. Jablan, Lj. Radovi\'{c}, and R. Sazdanovi\'{c}. \newblock Pyramidal knots and links and
their invariants.\newblock {\em MATCH Commun. Math. Comput. Chem.}, 65:541--580, 2011.

\bibitem{Jab2} S. Jablan, Lj. Radovi\'{c}, and R. Sazdanovi\'{c}. \newblock Tutte and Jones polynomials
of links, polyominoes and graphical recombination patterns.\newblock {\em J. Math.
Chem.}, 49(1):79--94, 2011.

\bibitem{Jack} B. Jackson. \newblock A zero-free interval for chromatic polynomials of graphs.\newblock {\em Combin. Probab.
Comput.}, 2:325--336, 1993.

\bibitem{Sokal1} B. Jackson, A. Procacci, and A.~D. Sokal. \newblock Complex zero-free regions at large $|q|$ for multivariate Tutte
polynomials (alias Potts-model partition functions) with general
complex edge weithts.\newblock {\em J. Combin. Theory Ser. B}, 103(1):21--45, 2013.


\bibitem{JZ} X. Jin and F. Zhang. \newblock Zeros of the Jones polynomial for multiple
crossing-twisted links. \newblock {\em J. Stat. Phys.}, 140:1054--1064, 2010.

\bibitem{JZ1} X. Jin, F. Zhang, F. Dong, and E.~G. Tay. \newblock Zeros of the Jones polynomial are
dense in the complex plane.\newblock {\em Electron. J. Comb.}, 17(1):R94, 2010.

\bibitem{Jones} V.~F.~R. Jones. \newblock A polynomial invariant for knots via von
Neumann algebras.\newblock {\em Bull. Amer. Math. Soc.}, 12:103--111, 1985.



\bibitem{Las} M. Las Vergnas. \newblock Eulerian circuits of 4-valent graphs imbedded in surfaces. \newblock In {\em  Algebaraic Methods in Graph Theory},\newblock{\em Colloquia Mathematica Societais J\`{a}nos Bolyai}, Vol. 25, pages 451-477. \newblock Szeged, Hungary, 1978.

\bibitem{Lin2} X.-S. Lin. \newblock Zeros of the Jones polynomial.
See \url{http://math.ucr.edu/~xl/abs-jk.pdf}

\bibitem{Mar} P. Martin. \newblock Remarkable valuation of the dichromatic polynomial of planar multigraphs. \newblock {\em J. Combin. Theory Ser. B}, 24:195--226, 1978.




\bibitem{welsh} S.~D. Noble and D.~J.~A. Welsh. \newblock Knot graphs.\newblock {\em J. Graph
Theory}, 34:100--111, 2000.

\bibitem{RR} P. Rosenstiehl and R.~C. Read. \newblock On the principal edge-tripartition of a graph.\newblock {\em Ann. Discrete Math.},
3:195--226, 1978.

\bibitem{SH} H. Shank. \newblock The theory of left-right paths. \newblock In {\em A. Penfold Street, W.~D. Wallis (Eds.),
Combinatorial Math. III}, \newblock {\em Lecture Notes in Math.}, Vol. 452, pages 42--54. Springer,
Berlin, 1975.

\bibitem{Sokal} A.~D. Sokal. \newblock Bounds on the complex zeros of
(di)chromatic polynomials and Potts-model partitions functions. \newblock {\em Combin. Prob. Comput.}, 10:41--77, 2001.

\bibitem{Sokal2} A.~D. Sokal. \newblock Chromatic polynomials, Potts models and all that. \newblock {\em Physica A}, 279:324--332, 2000.

\bibitem{Th} M.~B. Thistlethwaite. \newblock A spanning tree expansion of the
Jones polynomial.\newblock {\em Topology}, 26:297--309, 1987.



\bibitem{Tao} Z.~X. Tao. \newblock On the zeros of Jones polynomial.\newblock {\em Chinese Ann. Math. Ser.
A}, 32(1): 63--70, 2011.

\bibitem{Thom}C. Thomassen. \newblock The zero-free intervals for chromatic polynomials of graphs.\newblock {\em Combin.
Probab. Comput.}, 6:497--506, 1997.


\bibitem{Tutte} W.~T. Tutte. \newblock A contribution to the theory of chromatic
polynomials. \newblock {\em Canad. J. Math.}, 6:80--91, 1954.

\bibitem{Wu} F.~Y. Wu and J. Wang. \newblock Zeros of the Jones polynomial. \newblock {\em Physica A}, 296:483--494, 2001.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{thebibliography}

\end{document}















