Bounds on the kth multi-g base index of nearly reducible sign pattern matrices

Li et al. [On the period and base of a sign pattern matrix, Linear Algebra Appl. 212/213 (1994) 101-120.] extended the concepts of the base and period from nonnegative matrices to powerful sign pattern matrices. Then, Shao and You [Bound on the basis of irreducible generalized sign pattern matrices, Linear Algebra Appl. 427 (2007) 285-300.] extended the concepts of the base from powerful sign pattern matrices to non-powerful irreducible sign pattern matrices. In this paper we mainly study the kth multi-g base index for non-powerful primitive nearly reducible sign pattern matrices. We obtain sharp upper bounds, together with a complete characterization of the equality cases of the kth multi-g base index for primitive nearly reducible generalized sign pattern matrices. We also show that there exist “gaps” in the kth multi-g base index set of the classes of such matrices.     

The enumeration of planar graphs via Wick's theorem

A seminal technique of theoretical physics called Wick's theorem interprets the Gaussian matrix integral of the products of the trace of powers of Hermitian matrices as the number of labelled maps with a given degree sequence, sorted by their Euler characteristics. This leads to the map enumeration results analogous to those obtained by combinatorial methods. In this paper we show that the enumeration of the graphs embeddable on a given 2-dimensional surface (a main research topic of contemporary enumerative combinatorics) can also be formulated as the Gaussian matrix integral of an ice-type partition function. Some of the most puzzling conjectures of discrete mathematics are related to the notion of the cycle double cover. We express the number of the graphs with a fixed directed cycle double cover as the Gaussian matrix integral of an Ihara-Selberg-type function.     

Domination in bipartite graphs

We prove that the domination number of a graph of order n and minimum degree at least 2 that does not contain cycles of length 4, 5, 7, 10 or 13 is at most . Furthermore, we derive upper bounds on the domination number of bipartite graphs of given minimum degree.     

Intersection graphs of ideals of rings

In this paper, we consider the intersection graph G(R) of nontrivial left ideals of a ring R. We characterize the rings R for which the graph G(R) is connected and obtain several necessary and sufficient conditions on a ring R such that G(R) is complete. For a commutative ring R with identity, we show that G(R) is complete if and only if G(R[x]) is also so. In particular, we determine the values of n for which is connected, complete, bipartite, planar or has a cycle. Next, we characterize finite graphs which arise as the intersection graphs of and determine the set of all non-isomorphic graphs of for a given number of vertices. We also determine the values of n for which the graph of is Eulerian and Hamiltonian.     

Hamilton cycles in graph bundles over a cycle with tree as a fibre

A sufficient and necessary condition for the existence of a Hamilton cycle in a graph bundle with a cycle as a base and a tree as a fibre is obtained.     

On the existence of graphs of diameter two and defect two

In the context of the degree/diameter problem, the ‘defect’ of a graph represents the difference between the corresponding Moore bound and its order. Thus, a graph with maximum degree d and diameter two has defect two if its order is n=d²−1. Only four extremal graphs of this type, referred to as (d,2,2)-graphs, are known at present: two of degree d=3 and one of degree d=4 and 5, respectively. In this paper we prove, by using algebraic and spectral techniques, that for all values of the degree d within a certain range, (d,2,2)-graphs do not exist.The enumeration of (d,2,2)-graphs is equivalent to the search of binary symmetric matrices A fulfilling that AJ_n=dJ_n and A²+A+(1−d)I_n=J_n+B, where J_n denotes the all-one matrix and B is the adjacency matrix of a union of graph cycles. In order to get the factorization of the characteristic polynomial of A in Q[x], we consider the polynomials F_i,d(x)=f_i(x²+x+1−d), where f_i(x) denotes the minimal polynomial of the Gauss period , being ζ_i a primitive ith root of unity. We formulate a conjecture on the irreducibility of F_i,d(x) in Q[x] and we show that its proof would imply the nonexistence of (d,2,2)-graphs for any degree d>5.     

基于Cycle Spinning Contourlet变换和总变分最小化的遥感图像去噪算法(英文)

针对大部分已有的遥感图像去噪算法在去噪的同时不能有效的保留细节和增强边缘,提出了一种基于Cycle Spinning Contourlet变换和总变分最小化的图像去噪新算法.该算法依据了Cycle Spinning Contourlet变换能够很好的保留原始图像的细节和纹理信息,而总变分最小化方法具有在去噪的同时增强图像边缘的特性,因此使用所提出的融合规则对两种算法去噪后的图像进行融合能够取得更好的增强效果.通过对比,实验结果表明该算法不仅能在很大程度上削弱分别由平移不变Contourlet变换和总变分最小化的图像去噪方法产生的伪吉布斯现象和阶梯效应,而且视觉效果和PSNR值均优于其它方法,同时该算法能够保留更多的光谱信息,因此该算法是一种有效的遥感图像去噪算法.     

Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define $V_i?\{v\in V\left(G\right):c\left(v\right)=i\}$ for $i=1$ and $2.$ We say that $G$ is $(d_1,d_2)$-colorable if $G$ has a 2-coloring such that $V_i$ is an empty set or the induced subgraph $G\left[V_i\right]$ has the maximum degree at most $d_i$ for $i=1$ and $2.$ Let $G$ be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for every positive integer $k.$ Moreover, we construct non-$(1,k)$-colorable planar graphs without 4-cycles and 5-cycles for every positive integer $k.$ In contrast, we prove that $G$ is $(d_1,d_2)$-colorable where $(d_1,d_2)=(4,4),(3,5),$ and $(2,9).$     

A 4/3-approximation for TSP on cubic 3-edge-connected graphs

For a 3-edge-connected cubic graph $G=(V,E)$, we give an algorithm to construct a connected Eulerian subgraph of $2G$ using at most $?4\left|V\right|∕3?$ edges.     

Fundamental group and cycle space of dual graphs and applications

In this work, we study the fundamental group of dual graph of a planar graph. Moreover, we show that a planar graph G has no cut vertex if and only if N(Π(D(G))) = N(Π(D(G − v))) − 1 for any v ∈ V(G). Some applications relevant to quantum space time are indicated. Our results generalize and extend results in paper [1] [S.I. Nada, E.H. Hamouda, Fundamental group of dual graphs and applications to quantum space time, Chaos Soliton Fractals 42 (2009) 500-503].