Search

We characterize the simple connected graphs with the second largest eigenvalue less than 1/2, which consists of 13 classes of specific graphs. These 13 classes hint that $c_{2}\in [1/2, \sqrt{2+\sqrt{5}}]$, where $c_2$ is the minimum real number $c$ for which every real number greater than $c$ is a limit point in the set of the second largest eigenvalues of the simple connected graphs. We leave it as a problem., Comment: 36 pages, 2 tables

It is known that, for any $k$-list assignment $L$ of a graph $G$, the number of $L$-list colorings of $G$ is at least the number of the proper $k$-colorings of $G$ when $k>(m-1)/\ln(1+\sqrt{2})$. In this paper, we extend the Whitney's broken cycle theorem to $L$-colorings of signed graphs, by which we show that if $k> \binom{m}{3}+\binom{m}{4}+m-1$ then, for any $k$-assignment $L$, the number of $L$-colorings of a signed graph $\Sigma$ with $m$ edges is at least the number of the proper $k$-colorings of $\Sigma$. Further, if $L$ is $0$-free (resp., $0$-included) and $k$ is even (resp., odd), then the lower bound $\binom{m}{3}+\binom{m}{4}+m-1$ for $k$ can be improved to $(m-1)/\ln(1+\sqrt{2})$., Comment: 13 pages

A connected graph $G$ is called strongly Menger edge connected if $G$ has min\{deg$_G(x)$, deg$_G(y)$\} edge-disjoint paths between any two distinct vertices $x$ and $y$ in $G$. In this paper, we consider two types of strongly Menger edge connectivity of the line graphs of $n$-dimensional hypercube-like networks with faulty edges, namely the $m$-edge-fault-tolerant and $m$-conditional edge-fault-tolerant strongly Menger edge connectivity. We show that the line graph of any $n$-dimensional hypercube-like network is $(2n-4)$-edge-fault-tolerant strongly Menger edge connected for $n\geq 3$ and $(4n-10)$-conditional edge-fault-tolerant strongly Menger edge connected for $n\geq 4$. The two bounds for the maximum number of faulty edges are best possible., Comment: 18 pages, 4 figures

For two graphs $J$ and $H$, the generalized Tur\'{a}n number, denoted by $ex(n,J,H)$, is the maximum number of copies of $J$ in an $H$-free graph of order $n$. A linear forest $F$ is the disjoint union of paths. In this paper, we determine the number $ex(n,S_r,F)$ when $n$ is large enough and characterize the extremal graphs attaining $ex(n,S_r,F)$, which generalizes the results on $ex(n, S_r, P_k)$, $ex(n,K_2,(k+1) P_2)$ and $ex(n,K^*_{1,r},(k+1) P_2)$. Finally, we pose the problem whether the extremal graph for $ex(n,J,F)$ is isomorphic to that for $ex(n,S_r,F)$, where $J$ is any graph such that the number of $J$'s in any graph $G$ does not decrease by shifting operation on $G$., Comment: 14 pages, 2 figures

For two graphs $G$ and $H$, let $r(G,H)$ and $r_*(G,H)$ denote the Ramsey number and star-critical Ramsey number of $G$ versus $H$, respectively. In 1996, Li and Rousseau proved that $r(K_{m},F_{t,n})=tn(m-1)+1$ for $m\geq 3$ and sufficiently large $n$, where $F_{t,n}=K_{1}+nK_{t}$. Recently, Hao and Lin proved that $r(K_{3},F_{3,n})=6n+1$ for $n\geq 3$ and $r_{\ast}(K_{3},F_{3,n})=3n+3$ for $n\geq 4$. In this paper, we show that $r(K_{m}, sF_{t,n})=tn(m+s-2)+s$ for sufficiently large $n$ and, in particular, $r(K_{3}, sF_{t,n})=tn(s+1)+s$ for $t\in\{3,4\},n\geq t$ and $s\geq1$. We also show that $r_{\ast}(K_{3}, F_{4,n})=4n+4$ for $n\geq 4$ and establish an upper bound on $r(F_{2,m},F_{t,n})$., Comment: 9 pages

The Sombor index of a graph $G$ was recently introduced by Gutman from the geometric point of view, defined as $SO(G)=\sum_{uv\in E(G)}\sqrt{d(u)^2+d(v)^2}$, where $d(u)$ is the degree of a vertex $u$. For two real numbers $\alpha$ and $\beta$, the $\alpha$-Sombor index and general Sombor index of $G$ are two generalized forms of the Sombor index defined as $SO_\alpha(G)=\sum_{uv\in E(G)}(d(u)^{\alpha}+d(v)^{\alpha})^{1/\alpha}$ and $SO_\alpha(G;\beta)=\sum_{uv\in E(G)}(d(u)^{\alpha}+d(v)^{\alpha})^{\beta}$, respectively. A $k$-polygonal cactus is a connected graph in which every block is a cycle of length $k$. In this paper, we establish a lower bound on $\alpha$-Sombor index for $k$-polygonal cacti and show that the bound is attained only by chemical $k$-polygonal cacti. The extremal $k$-polygonal cacti for $SO_\alpha(G;\beta)$ with some particular $\alpha$ and $\beta$ are also considered., Comment: 16 pages,1 figure

Whitney proved in 1931 that every 4-connected planar triangulation is hamiltonian. Later in 1979, Hakimi, Schmeichel and Thomassen conjectured that every such triangulation on $n$ vertices has at least $2(n - 2)(n - 4)$ hamiltonian cycles. Along this direction, Brinkmann, Souffriau and Van Cleemput established a linear lower bound on the number of hamiltonian cycles in 4-connected planar triangulations. In stark contrast, Alahmadi, Aldred and Thomassen showed that every 5-connected triangulation of the plane or the projective plane has exponentially many hamiltonian cycles. This gives the motivation to study the number of hamiltonian cycles of 4-connected triangulations with few 4-separators. Recently, Liu and Yu showed that every 4-connected planar triangulation with $O(n / \log n)$ 4-separators has a quadratic number of hamiltonian cycles. By adapting the framework of Alahmadi et al. we strengthen the last two aforementioned results. We prove that every 4-connected planar or projective planar triangulation with $O(n)$ 4-separators has exponentially many hamiltonian cycles.

Let $G$ be a graph embedded on an orientable surface. Given a class ${\cal C}$ of facial circuits of $G$ as a forbidden class, we give a sufficient-necessary condition for that an $\alpha$-orientation (orientation with prescribed out-degrees) of $G$ can be transformed into another by a sequence of flips on non-forbidden circuits and further give an explicit formula for the minimum number of such flips. We also consider the connection among all $\alpha$-orientations by defining a directed graph ${\bf D}({\cal C})$, namely the ${\cal C}$-forbidden flip graph. We show that if ${\cal C}\not=\emptyset$, then ${\bf D}({\cal C})$ has exactly $|O(G,{\cal C})|$ components, each of which is the cover graph of a distributive lattice, where $|O(G,{\cal C})|$ is the number of the $\alpha$-orientations that has no counterclockwise facial circuit other than that in ${\cal C}$. If ${\cal C}=\emptyset$, then every component of ${\bf D}({\cal C})$ is strongly connected. This generalizes the corresponding results of Felsner and Propp for the case that ${\cal C}$ consists of a single facial circuit., Comment: 16 pages, 4 figures

Let $2^{[n]}$ and $\binom{[n]}{i}$ be the power set and the class of all $i$-subsets of $\{1,2,\cdots,n\}$, respectively. We call two families $\mathscr{A}$ and $\mathscr{B}$ cross-intersecting if $A\cap B\neq \emptyset$ for any $A\in \mathscr{A}$ and $B\in \mathscr{B}$. In this paper we show that, for $n\geq k+l,l\geq r\geq 1,c>0$ and $\mathscr{A}\subseteq \binom{[n]}{k},\mathscr{B}\subseteq \binom{[n]}{l}$, if $\mathscr{A}$ and $\mathscr{B}$ are cross-intersecting and $\binom{n-r}{l-r}\leq|\mathscr{B}|\leq \binom{n-1}{l-1}$, then $$|\mathscr{A}|+c|\mathscr{B}|\leq \max\left\{\binom{n}{k}-\binom{n-r}{k}+c\binom{n-r}{l-r},\ \binom{n-1}{k-1}+c\binom{n-1}{l-1}\right\}$$ and the families $\mathscr{A}$ and $\mathscr{B}$ attaining the upper bound are also characterized. This generalizes the corresponding result of Hilton and Milner for $c=1$ and $r=k=l$, and implies a result of Tokushige and the second author (Theorem 1.3)., Comment: 12 pages

A mixed graph $G$ is a graph obtained from a simple undirected graph by orientating a subset of edges. $G$ is self-converse if it is isomorphic to the graph obtained from $G$ by reversing each directed edge. For two mixed graphs $G$ and $H$ with Hermitian adjacency matrices $A(G)$ and $A(H)$, we say $G$ is $\mathbb{R}$\emph{-cospectral} to $H$ if, for any $y\in \mathbb{R}$, $yJ-A(G)$ and $yJ-A(H)$ have the same spectrum, where $J$ is the all-one matrix. A self-converse mixed graph $G$ is said to be determined by its generalized spectrum, if any self-converse mixed graph that is $R$-cospectral with $G$ is isomorphic to $G$. Let $G$ be a self-converse mixed graph of order $n$ such that $2^{-\lfloor n/2\rfloor}\det W$ (which is always a real or pure imaginary Gaussian integer) is square-free in $\mathbb{Z}[i]$, where $W=[e,Ae,\ldots,A^{n-1}e]$, $A=A(G)$ and $e$ is the all-one vector. We prove that, for any self-converse mixed graph $H$ that is $\mathbb{R}$-cospectral to $G$, there exists a Gaussian rational unitary matrix $U$ such that $Ue=e$, $U^*A(G)U=A(H)$ and $(1+i)U$ is a Gaussian integral matrix. In particular, if $G$ is an ordinary graph (viewed as a mixed graph) satisfying the above condition, then any self-converse mixed graph $H$ that is $\mathbb{R}$-cospectral to $G$ is $G$ itself (in the sense of isomorphism). This strengthens a recent result of the first author., Comment: 22 pages,1 figure

Let $n_{1}$ and $n_{2}$ be two integers with $n_{1},n_{2}\geq3$ and $G$ a graph of order $n=n_{1}+n_{2}$. As a generalization of Ore's degree condition for the existence of Hamilton cycle in $G$, El-Zahar proved that if $\delta(G)\geq \left\lceil\frac{n_{1}}{2}\right\rceil+\left\lceil\frac{n_{2}}{2}\right\rceil$ then $G$ contains two disjoint cycles of length $n_{1}$ and $n_{2}$. Recently, Yan et. al considered the problem by extending the degree condition to degree sum condition and proved that if $d(u)+d(v)\geq n+4$ for any pair of non-adjacent vertices $u$ and $v$ of $G$, then $G$ contains two disjoint cycles of length $n_{1}$ and $n_{2}$. They further asked whether the degree sum condition can be improved to $d(u)+d(v)\geq n+2$. In this paper, we give a positive answer to this question. Our result also generalizes El-Zahar's result when $n_{1}$ and $n_{2}$ are both odd.

Let $\Sigma$ be a signed graph where two edges joining the same pair of vertices with opposite signs are allowed. The zero-free chromatic number $\chi^*(\Sigma)$ of $\Sigma$ is the minimum even integer $2k$ such that $G$ admits a proper coloring $f\colon\,V(\Sigma)\mapsto \{\pm 1,\pm 2,\ldots,\pm k\}$. The zero-free list chromatic number $\chi^*_l(\Sigma)$ is the list version of zero-free chromatic number. $\Sigma$ is called zero-free chromatic-choosable if $\chi^*_l(\Sigma)=\chi^*(\Sigma)$. We show that if $\Sigma$ has at most $\chi^*(\Sigma)+1$ vertices then $\Sigma$ is zero-free chromatic-choosable. This result strengthens Noel-Reed-Wu Theorem which states that every graph $G$ with at most $2\chi(G)+1$ vertices is chromatic-choosable, where $\chi(G)$ is the chromatic number of $G$., Comment: 24 pages

Let $(G,\sigma)$ be any signed planar graph. We show that the Alon-Tarsi number of $(G,\sigma)$ is at most 5, generalizing a recent result of Zhu for unsigned case. In addition, if $(G,\sigma)$ is $2$-colorable then $(G,\sigma)$ has the Alon-Tarsi number at most 4. We also construct a signed planar graph which is $2$-colorable but not $3$-choosable., Comment: 14 pages,2 figures

It was conjectured by Ohba and confirmed recently by Noel et al. that, for any graph $G$, if $|V(G)|\le 2\chi(G)+1$ then $\chi_l(G)=\chi(G)$. This indicates that the graphs with high chromatic number are chromatic-choosable. We show that this is also the case for uniform hypergraphs and further propose a generalized version of Ohba's conjecture: for any $r$-uniform hypergraph $H$ with $r\geq 2$, if $|V(H)|\le r\chi(H)+r-1$ then $\chi_l(H)=\chi(H)$. We show that the condition of the proposed conjecture is sharp by giving two classes of $r$-uniform hypergraphs $H$ with $|V(H)|= r\chi(H)+r$ and $\chi_l(H)>\chi(H)$. To support the conjecture, we give two classes of $r$-uniform hypergraphs $H$ with $|V(H)|= r\chi(H)+r-1$ and prove that $\chi_l(H)=\chi(H)$., Comment: 18 pages

In contrast to ordinary graphs, the number of the nowhere-zero group-flows in a signed graph may vary with different groups, even if the groups have the same order. In fact, for a signed graph $G$ and non-negative integer $d$, it was shown that there exists a polynomial $F_d(G,x)$ such that the number of the nowhere-zero $\Gamma$-flows in $G$ equals $F_d(G,x)$ evaluated at $k$ for every Abelian group $\Gamma$ of order $k$ with $\epsilon(\Gamma)=d$, where $\epsilon(\Gamma)$ is the largest integer $d$ for which $\Gamma$ has a subgroup isomorphic to $\mathbb{Z}^d_2$. We focus on the combinatorial structure of $\Gamma$-flows in a signed graph and the coefficients in $F_d(G,x)$. We first define the fundamental directed circuits for a signed graph $G$ and show that all $\Gamma$-flows (not necessarily nowhere-zero) in $G$ can be generated by these circuits. It turns out that all $\Gamma$-flows in $G$ can be evenly classified into $2^{\epsilon(\Gamma)}$-classes specified by the elements of order 2 in $\Gamma$, each class of which consists of the same number of flows depending only on the order of the group. This gives an explanation for why the number of $\Gamma$-flows in a signed graph varies with different $\epsilon(\Gamma)$, and also gives an answer to a problem posed by Beck and Zaslavsky. Secondly, using an extension of Whitney's broken circuit theory we give a combinatorial interpretation of the coefficients in $F_d(G,x)$ for $d=0$, in terms of the broken bonds. As an example, we give an analytic expression of $F_0(G,x)$ for a class of the signed graphs that contain no balanced circuit. Finally, we show that the sets of edges in a signed graph that contain no broken bond form a homogeneous simplicial complex., Comment: The original version consists of 17 pages and 1 figure. The current version: 18 pages and 1 figure; a reference and a proof for Corollary 6.1 added; minor text modification made

Let $r$ be an integer with $r\ge 2$ and $G$ be a connected $r$-uniform hypergraph with $m$ edges. By refining the broken cycle theorem for hypergraphs, we show that if $k>\frac{m-1}{\ln(1+\sqrt{2})}\approx 1.135 (m-1)$ then the $k$-list assignment of $G$ admitting the fewest colorings is the constant list assignment. This extends the previous results of Donner, Thomassen and the current authors for graphs.

Whitney's broken circuit theorem gives a graphical example to reduce the number of the terms in the sum of the inclusion-exclusion formula by a predicted cancellation. So far, the known cancellations for the formula strongly depend on the prescribed (linear or partial) ordering on the index set. We give a new cancellation method, which does not require any ordering on the index set. Our method extends all the `ordering-based' methods known in the literatures and in general reduces more terms. As examples, we use our method to improve some relevant results on graph polynomials.

Felsner introduced a cycle reversal, namely the `flip' reversal, for \alpha-orientations (i.e., each vertex admits a prescribed out-degree) of a graph G embedded on the plane and further proved that the set of all the \alpha-orientations of G carries a distributive lattice with respect to the flip reversals. In this paper, we give an explicit formula for the minimum number of flips needed to transform one \alpha-orientation into another for graphs embedded on the plane or sphere, respectively., Comment: 15 pages, 4 figures