On the sphericity testing of single source digraphs

A digraph D=(V,A) is called spherical, if it has an upward embedding on the round sphere which is an embedding of D on the round sphere so that all edges are monotonic arcs and all point to a fixed direction, say to the north pole. It is easy to see that [S.M. Hashemi, Digraph embedding, Discrete Math. 233 (2001) 321-328] for upward embedding, plane and sphere are not equivalent, which is in contrast with the fact that they are equivalent for undirected graphs. On the other hand, it has been proved that sphericity testing for digraphs is an NP-complete problem [S.M. Hashemi, A. Kisielewicz, I. Rival, The complexity of upward drawings on spheres, Order 14 (1998) 327-363]. In this work we study sphericity testing of the single source digraphs. In particular, we shall present a polynomial time algorithm for sphericity testing of three connected single source digraphs.     

关于循环图的曲面嵌入

该文集中探讨循环图的曲面嵌入性质.决定了所有循环图的最小亏格(其中包括可定向亏格与不可定向亏格)和最大亏格.对于固定的整数l(≥3)和充分大的 自然数n,只有一种方式将4 -正则循环图C(n,l)嵌入到环面上使得其每一个面都是4 -边形.特别地,循环图$C(2l+2,l)$在加入若干条新边后可以同时将环面与Klein瓶进行三角剖分.     

Closed 2-cell embeddings of graphs with no V8-minors

A closed 2-cell embedding of a graph embedded in some surface is an embedding such that each face is bounded by a cycle in the graph. The strong embedding conjecture says that every 2-connected graph has a closed 2-cell embedding in some surface. In this paper, we prove that any 2-connected graph without V₈ (the Möbius 4-ladder) as a minor has a closed 2-cell embedding in some surface. As a corollary, such a graph has a cycle double cover. The proof uses a classification of internally-4-connected graphs with no V₈-minor (due to Kelmans and independently Robertson), and the proof depends heavily on such a characterization.     

A novel blind color images watermarking based on SVD

Since the color image watermark has more bit information, it is a challenging problem to design a robust and blind color watermarking scheme for copyright protection. In this paper, a blind watermarking scheme based on singular value decomposition (SVD) is proposed. By analyzing the orthogonal matrix U via SVD, it is found that there exists a strong similarity correlation between the second row first column element and the third row first column element. Hence, this paper utilizes this property for image watermarking. Firstly, the 4 × 4 non-overlapping pixels block of each component in color host image is processed by SVD. And then, the color watermark is embedded by slightly modifying the value of the second row first column element and the third row first column one of U matrix, and the modified relation can be utilized to extract watermark. Experimental results, compared with the related existing methods, show that the proposed color image scheme has stronger robustness against most common attacks such as image compression, filtering, cropping, noise adding, blurring, scaling and sharpening et al.     

Block based embedding of encrypted watermarks using singular value decomposition

Watermarking is a solution to the problem of copyright protection of multimedia documents over the Internet. This paper presents a block based watermarking scheme using the singular value decomposition (SVD) algorithm to embed encrypted watermarks into digital images. The paper compares between the traditional method of Liu and the proposed method for embedding encrypted watermarks. Also, a permutation based encryption algorithm and a diffusion based encryption algorithm are compared as the watermark encryption algorithms. Experimental results show that the proposed method is superior to the traditional method of Liu for embedding encrypted watermarks and extracting them efficiently under attacks. Results also show that it is preferred to use permutation based encryption algorithms than diffusion based encryption algorithms for watermark encryption due to their lower sensitivity to attacks.     

Metabolic networks classification and knowledge discovery by information granulation

Graphs are powerful structures able to capture topological and semantic information from data, hence suitable for modelling a plethora of real-world (complex) systems. For this reason, graph-based pattern recognition gained a lot of attention in recent years. In this paper, a general-purpose classification system in the graphs domain is presented. When most of the information of the available patterns can be encoded in edge labels, an information granulation-based approach is highly discriminant and allows for the identification of semantically meaningful edges. The proposed classification system has been tested on the entire set of organisms (5299) for which metabolic networks are known, allowing for both a perfect mirroring of the underlying taxonomy and the identification of most discriminant metabolic reactions and pathways. The widespread diffusion of graph (network) structures in biology makes the proposed pattern recognition approach potentially very useful in many different fields of application. More specifically, the possibility to have a reliable metric to compare different metabolic systems is instrumental in emerging fields like microbiome analysis and, more in general, for proposing metabolic networks as a universal phenotype spanning the entire tree of life and in direct contact with environmental cues.     

Bisecting a 4-connected graph with three resource sets

Let G=(V,E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T₁,T₂,…,T_k of nodes, called resource sets, where |T_i| is even for each i. The partition problem with k resource sets asks to find a partition V₁ and V₂ of the node set V such that the graphs induced by V₁ and V₂ are both connected and |V₁∩T_i|=|V₂∩T_i|=|T_i|/2 holds for each i=1,2,…,k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k=1. On the other hand, it is known that if G is (k+1)-connected for k=1,2, then a bisection exists for any given resource sets, and it has been conjectured that for k?3, a (k+1)-connected graph admits a bisection. In this paper, we show that for k=3, the conjecture does not hold, while if G is 4-connected and has K₄ as its subgraph, then a bisection exists and it can be found in O(|V|³log|V|) time. Moreover, we show that for an arc-version of the problem, the (k+1)-edge-connectivity suffices for k=1,2,3.     

Embedology

Mathematical formulations of the embedding methods commonly used for the reconstruction of attractors from data series are discussed. Embedding theorems, based on previous work by H. Whitney and F. Takens, are established for compact subsetsA of Euclidean space R^k. Ifn is an integer larger than twice the box-counting dimension ofA, then almost every map fromR ^k toR ⁿ , in the sense of prevalence, is one-to-one onA, and moreover is an embedding on smooth manifolds contained withinA. IfA is a chaotic attractor of a typical dynamical system, then the same is true for almost everydelay-coordinate map fromR ^k toR ⁿ . These results are extended in two other directions. Similar results are proved in the more general case of reconstructions which use moving averages of delay coordinates. Second, information is given on the self-intersection set that exists whenn is less than or equal to twice the box-counting dimension ofA.     

An identity for 4-spacetimes embedded intoE 5

We show that if a 4-spacetimeV ₄ can be embedded intoE ₅ then, ifb _ijis the second fundamental form tensor associated withV ₄, the quantity (traceb)·b _ij ^/−1 depends only on intrinsic geometric properties of the spacetime. Such fact is used to obtain a necessary condition for the embedding of aV ₄ intoE ₅.