Search

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)., 12 pages

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

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

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

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S has an in-neighbor in S. A dominating set S of D is called a total dominating set of D if the subdigraph induced by S has no isolated vertices. The total domination number of D, denoted by γt(D), is the minimum cardinality of a total dominating set of D. We show that for any connected digraph D of order n ≥ 3,γt(D) + γt(D−) ≤ 5n/3, where D− is the converse of D. Furthermore, we characterize the oriented trees for which the equality holds.Mathematics Subject Classification (2010): 05C69, 05C20.Key words: Total domination number, oriented tree, digraph, converse.

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.

The number of transmission messages is small when the traditional power system monitoring methods collect signals, Therefore, a fault dynamic monitoring method of intelligent power system telecontrol dispatching based on improved fault tree is proposed. The telecontrol communication model of intelligent power system is constructed. The communication signal of telecontrol dispatching channel is collected. The parameter of signal time-domain characteristic is measured. The time-domain waveform can pass through the zero period to get the carrier frequency range, judge whether the system telecontrol dispatching has fault, and analyze the fault mode by improving the graphical logic deduction of fault tree. A comparative experiment is carried out. Compared with the traditional methods, the results show that the design method can improve the number of packet transmission per unit time, increase the network traffic, and ensure that the communication network has very low load in the dynamic monitoring process.

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

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.

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.

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

Due to the finite restricted ground TT&C resources, more and more conflicts appear caused by the increasing TT&C requirements of multi-satellite. The priority determination of TT&C arcs is affected by many factors. It is an important criterion of conflicts elimination for resources scheduling. This paper analyzes the main factors in practice, and put forward a method of using artificial neural network to solve the problem of uncertain information processing. Through training and learning the neural network time after time, established neural network can achieve the coefficients of the affected factors and the final priority of TT&C arcs. Simulation results demonstrate that the method of arc priority determination based on Back-Propagation (BP) neural network is feasible for the scheduling of TT&C resources and the adjustment in emergency.

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

Felsner introduced a cycle reversal, namely the `flip' reversal, for ��-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 ��-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 ��-orientation into another for graphs embedded on the plane or sphere, respectively., 15 pages, 4 figures