A CLASS OF HAMILTONIAN AND EDGE SYMMETRIC CAYLEY GRAPHS ON SYMMETRIC GROUPS

Let S\-n be the symmetric group, g\++\-i=(123i),g\+-\-i=(1i32) and M\++\-n={g\++\-i∶4≤i≤n}, then M\++\-n is a minimal generating set of S\-n ,where n ≥5.It is proved that Cayley graph Cay( S\-n,M\++\-n∪M\+-\-n) is Hamiltonian and edge symmetric.

Effect of graph generation on slope stability analysis based on graph theory

Limit equilibrium method （LEM） and strength reduction method （SRM） are the most widely used methods for slope stability analysis. However, it can be noted that they both have some limitations in practical application. In the LEM, the constitutive model cannot be considered and many assumptions are needed between slices of soil/rock. The SRM requires iterative calculations and does not give the slip surface directly. A method for slope stability analysis based on the graph theory is recently developed to directly calculate the minimum safety factor and potential critical slip surface according to the stress results of numerical simulation. The method is based on current stress state and can overcome the disadvantages mentioned above in the two traditional methods. The influences of edge generation and mesh geometry on the position of slip surface and the safety factor of slope are studied, in which a new method for edge generation is proposed, and reasonable mesh size is suggested. The results of benchmark examples and a rock slope show good accuracy and efficiency of the presented method.

Algebraic Properties of Edge Ideals of Some Vertex-Weighted Oriented Cyclic Graphs

We provide some exact formulas for the projective dimension and regularity of edge ideals associated to some vertex-weighted oriented cyclic graphs with a common vertex or edge.These formulas axe functions in the weight of the vertices,and the numbers of edges and cycles.Some examples show that these formulas are related to direction selection and the assumption that w(x)≥2 for any vertex x cannot be dropped.

A Note on List Edge and List Total Coloring of Planar Graphs without Adjacent Short Cycles

LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl（G）=Δand the list total chromatic numberχl（G）=Δ＋1.

Robust interactive image segmentation via graph-based manifold ranking

Interactive image segmentation aims at classifying the image pixels into foreground and background classes given some foreground and background markers. In this paper, we propose a novel framework for interactive image segmentation that builds upon graph-based manifold ranking model, a graph-based semi-supervised learning technique which can learn very smooth functions with respect to the intrinsic structure revealed by the input data. The final segmentation results are improved by overcoming two core problems of graph construction in traditional models: graph structure and graph edge weights. The user provided scribbles are treated as the must-link and must-not-link constraints. Then we model the graph as an approximatively k-regular sparse graph by integrating these constraints and our extended neighboring spatial relationships into graph structure modeling. The content and labels driven locally adaptive kernel parameter is proposed to tackle the insufficiency of previous models which usually employ a unified kernel parameter. After the graph construction,a novel three-stage strategy is proposed to get the final segmentation results. Due to the sparsity and extended neighboring relationships of our constructed graph and usage of superpixels, our model can provide nearly real-time, user scribble insensitive segmentations which are two core demands in interactive image segmentation. Last but not least, our framework is very easy to be extended to multi-label segmentation,and for some less complicated scenarios, it can even get the segmented object through single line interaction. Experimental results and comparisons with other state-of-the-art methods demonstrate that our framework can efficiently and accurately extract foreground objects from background.

Super-Edge-Connectivity of G(k,d,s)(s≥k/2)

A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v｜v=1（）kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=（u1…uk）and v=（v1…vk）are adjacent if and only if us＋i=vi or vs＋i=ui（i=1,…,k-s）.In particular G（k,d,1）is just an undirected de Bruijn graph.In this paper,we show that the diameter of G（k,d,s）is k s,the girth is 3.Finally,we prove that G（k,d,s）（s≥k/2）is super-λ.

Approximation Algorithm for the Balanced 2-Correlation Clustering Problem

The Correlation Clustering Problem(CorCP) is a significant clustering problem based on the similarity of data.It has significant applications in different fields,such as machine learning,biology,and data mining,and many different problems in other areas.In this paper,the Balanced 2-CorCP(B2-CorCP) is introduced and examined,and a new interesting variant of the CorCP is described.The goal of this clustering problem is to partition the vertex set into two clusters with equal size,such that the number of disagreements is minimized.We first present a polynomial time algorithm for the B2-CorCP on M-positive edge dominant graphs(M≥ 3).Then,we provide a series of numerical experiments,and the results show the effectiveness of our algorithm.