Short Cycle Structure of Graphs on Surfaces （1） -the Uniqueness Theorems

In this paper we investigate cycle base structures of a （weighted） graph and show that much information of short cycles is contained in a MCB （minimum cycle base）. After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be a MCB. Further more, we show that the structure of MCB in a （weighted） graph is unique. In the case of nonnegative weight, every pair of MCB have the same number of k-cycles for each integer k ≥ 3. The property is also true for those having longest length （although much work has been down in evaluating MCB, little is known for those having longest length）.     

Short cycle structures for graphs on surfaces and an open problem of Mohar and Thomassen

In this paper we investigate cycle base structures of a (weighted) graph and show that much information of short cycles is contained in an MCB (i.e., minimum cycle base). After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be an MCB. Furthermore, we show that the structure of MCB in a (weighted) graph is unique. The property is also true for those having a longest length (although much work has been down in evaluating MCB, little is known for those having a longest length). We use those methods to find out some unknown properties for short cycles sharing particular properties in (unweighted) graphs. As applications, we determine the structures of short cycles in an embedded graph and show that there exist polynomially bounded algorithms in finding a shortest contractible cycle and a shortest two-sided cycle provided such cycles exist. Those answer an open problem of B. Mohar and C. Thomassen.     

On some cycles in linearized Wenger graphs

Let ${\mathbb{F}}_q$ be the finite field of $q$ elements for prime power $q$ and let $p$ be the character of ${\mathbb{F}}_q$. For any positive integer $m$, the linearized Wenger graph $L_m\left(q\right)$ is defined as follows: it is a bipartite graph with the vertex partitions being two copies of the $(m+1)$-dimensional vector space ${\mathbb{F}}_q^{m+1}$, and two vertices $p=\left(p\left(1\right),\dots ,p(m+1)\right)$ and $l=\left[l\left(1\right),\dots ,l(m+1)\right]$ being adjacent if $p\left(i\right)+l\left(i\right)=p\left(1\right){\left(l\left(1\right)\right)}^{p^{i?2}}$, for all $i=2,3,\dots ,m+1$. In this paper, we show that for any positive integers $m$ and $k$ with $3\le k\le p^2$, $L_m\left(q\right)$ contains even cycles of length $2k$ which is an open problem put forward by Cao et al. (2015).     

Homogeneous Embeddings of Cycles in Graphs

If G and H are vertex-transitive graphs, then the framing number fr(G,H) of G and H is defined as the minimum order of a graph every vertex of which belongs to an induced G and an induced H. This paper investigates fr(C _m,C _n) for m<n. We show first that fr(C _m,C _n)≥n+2 and determine when equality occurs. Thereafter we establish general lower and upper bounds which show that fr(C _m,C _n) is approximately the minimum of and n+n/m. Received: June 12, 1996 / Revised: June 2, 1997     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.     

Cycle embedding in star graphs with more conditional faulty edges

The star graph is one of the most attractive interconnection networks. The cycle embedding problem is widely discussed in many networks, and edge fault tolerance is an important issue for networks since edge failures may occur when a network is put into use. In this paper, we investigate the cycle embedding problem in star graphs with conditional faulty edges. We show that there exist fault-free cycles of all even lengths from 6 to n! in any n-dimensional star graph S_n (n ? 4) with ?3n − 10 faulty edges in which each node is incident with at least two fault-free edges. Our result not only improves the previously best known result where the number of tolerable faulty edges is up to 2n − 7, but also extends the result that there exists a fault-free Hamiltonian cycle under the same condition.     

Minor and minimum cycle bases of a 3-connected planar graph

In this paper, we prove that if any set of ｜E（G）｜- ｜V（G）｜ ＋ 1 facial cycles of a 3-connected planar graph G embedded in the plane doesn＇t form a minimum cycle base of G, then any minimum cycle base of G contains a separating cycle, and G has a minor isomorphic to T6, where T6 is the graph obtained from the complete graph K6 by deleting a path with four edges.     

Distance Between α-Orientations of Plane Graphs by Facial Cycle Reversals

Cycle reversal had been shown as a powerful method to deal with the relation among orientations of a graph since it preserves the out-degree of each vertex and the connectivity of the orientations. A facial cycle reversal on an orientation of a plane graph is an operation that reverses all the directions of the edges of a directed facial cycle. An orientation of a graph is called an α-orientation if each vertex admits a prescribed out-degree. In this paper, we give an explicit formula for the minimum number of the facial cycle reversals needed to transform one α-orientation into another for plane graphs.     

ContributionsTriangular embeddings of Kn−Km with unboundedly large m

The author has proposed methods of constructing index 2 and 3 current graphs generating triangular embeddings of graphs K_n−K_m with unboundedly large m (as n increases). As a result, triangular embeddings of graphs of many families of graphs K_n−K_m with unboundedly large m were constructed. The paper gives a survey of these results and a short explanation of the methods.     

EMBEDDINGS OF ONE KIND OF GRAPHS

The purpose of this paper is to display a new kind of simple graphs which belong to B. inwhich any graph has its orientable genus n,n≥3. Furthermore, for any integer k,1≤k≤n,there exists a graph B^kn of B. such that the non-orientable genus of B^kn is k.     

完全偶图的圈基内插性质

图G的一个圈基的长度是该圈基的所有圈的长度之和。设C^-、C^ 分别是G的最小、最大圈基长度,如果对任一偶数C,C^-＜C＜C^ ,都存在G的一个长为C的圈基,则称G具有偶圈基内插性质,本证明了,完全偶图Km,n具有偶圈基内插性质。     

Applying a combinatorial determinant to count weighted cycle systems in a directed graph

One method for counting weighted cycle systems in a graph entails taking the determinant of the identity matrix minus the adjacency matrix of the graph. The result of this operation is the sum over cycle systems of −1 to the power of the number of disjoint cycles times the weight of the cycle system. We use this fact to reprove that the determinant of a matrix of much smaller order can be computed to calculate the number of cycle systems in a hamburger graph.     

提高长尾数据知识图谱补全性能的一种新算法

知识图谱是众多智能应用中一种重要的语义数据, 但其数据的不完备性给实际应用带来了很多困难, 因此需要对知识图谱中缺失的语义信息进行补全。知识图谱嵌入是知识图谱补全的重要方法之一, 这类方法通常在非长尾数据情况下具有较好的效果, 但在长尾数据情况下其效果较差。由于非长尾数据的语义较丰富, 为了提升长尾数据情况下知识图谱补全效果, 本文将非长尾数据作为监督知识迁移到长尾数据中, 提出了一种新的算法——融入期望最大化算法思想的双重嵌入方法, 来改进长尾数据的知识图谱补全性能, 进而提高其实际应用效果。通过在FB15K数据集中进行链接预测任务的对比实验, 实验结果表明本文提出的融入期望最大化算法思想的双重嵌入方法效果较好。     

Edge-bipancyclicity of a hypercube with faulty vertices and edges

A bipartite graph G=(V,E) is said to be bipancyclic if it contains a cycle of every even length from 4 to |V|. Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let F_v (respectively, F_e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Q_n. In this paper, we show that every edge of Q_n-F_v-F_e lies on a cycle of every even length from 4 to 2ⁿ-2|F_v| even if |F_v|+|F_e|?n-2, where n?3. Since Q_n is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal.