A new color image cryptosystem via hyperchaos synchronization

This paper proposes a novel color image cryptosystem based on synchronization of two different six-dimensional hyperchaotic systems. In the transmitter end, we apply the drive system to generate the diffusion matrices and scrambling ones, which are used to change the image pixel value and position, respectively. Thus the ciphered image is obtained. In the receiver, synchronization of two nonidentical hyperchaotic systems can be achieved by designing the appropriate controllers. The response system is employed to yield the corresponding diffusion matrices and scrambling ones using the same generation method in the encryption algorithm. Then the cipher-image can be decrypted by the decryption algorithm, which is similar to that of the encryption process but in the reversed order. The experimental results show that the presented image cryptosystem has high security and can resist noise and crop attacks.     

1‐Factor and Cycle Covers of Cubic Graphs

Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let be the set of edges contained in precisely i members of the k 1‐factors. Let be the smallest over all lists of k 1‐factors of G. Any list of three 1‐factors induces a core of a cubic graph. We use results on the structure of cores to prove sufficient conditions for Berge‐covers and for the existence of three 1‐factors with empty intersection. Furthermore, if , then is an upper bound for the girth of G. We also prove some new upper bounds for the length of shortest cycle covers of bridgeless cubic graphs. Cubic graphs with have a 4‐cycle cover of length and a 5‐cycle double cover. These graphs also satisfy two conjectures of Zhang 18 . We also give a negative answer to a problem stated in 18 .     

Nonvertex‐Balanced Factors in Random Graphs

We prove part of a conjecture by Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28.) regarding threshold functions for the existence of an H‐factor in a random graph . We prove that the conjectured threshold function is correct for any graph H which is not covered by its densest subgraphs. We also demonstrate that the main result of Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28) generalizes to multigraphs, digraphs, and a multipartite model.     

On independent sets in random graphs

The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be with high probability, with in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size , i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size for any fixed (independent of both d and n). In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point . Roughly speaking, we prove that independent sets of size form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015     

Fundamental Groups of Graphs of Cyclic Subgroup Separable and Weakly Potent Groups

We give a characterization of the cyclic subgroup separability and weak potency of the fundamental group of a graph of polycyclic-by-finite groups and free-by-finite groups amalgamating edge subgroups of the form × D,where h has infinite order and D is finite.     

关于图的同构判定方法的探讨

对于两图的同构的判定方法进行较深入的探讨,给出判定两图同构和判定两图不同构的几种方法,并对其判定方法的优劣进行比较.     

关于两个图的一类新连接图的谱

给定2个图G1和G2,设G1的边集E(G1)={e1,e2,?,em1},则图G1⊙G2可由一个G1,m1个G2通过在G1对应的每条边外加一个孤立点,新增加的点记为U={u1,u2,?,um1},将ui分别与第i个G2的所有点以及G1中的边ei的端点相连得到,其中i=?1,2,?,m1。得到：（i）当G1是正则图,G2是正则图或完全二部图时,确定了G1⊙G2的邻接谱（A-谱）。（ii）当G1是正则图,G2是任意图时,给出了G1⊙G2的拉普拉斯谱（L-谱）。（iii）当G1和G2都是正则图时,给出了G1⊙G2的无符号拉普拉斯谱（Q-谱）。作为以上结论的应用,构建了无限多对A-同谱图、L-同谱图和Q-同谱图;同时当G1是正则图时,确定了G1⊙G2支撑树的数量和Kirchhoff指数。