Hamiltonian and long paths in bipartite graphs with connectivity

Let G be a graph, $\nu (G)$ the order of G, $\kappa (G)$ the connectivity of G and k a positive integer such that $k\le (\nu (G)?2)/2$. Then G is said to be k-extendable if it has a matching of size k and every matching of size k extends to a perfect matching of G. A Hamiltonian path of a graph G is a spanning path of G. A bipartite graph G with vertex sets $V_1$ and $V_2$ is defined to be Hamiltonian-laceable if such that $|V_1|=|V_2|$ and for every pair of vertices $p\in V_1$ and $q\in V_2$, there exists a Hamiltonian path in G with endpoints p and q, or $|V_1|=|V_2|+1$ and for every pair of vertices $p,q\in V_1,p\ne q$, there exists a Hamiltonian path in G with endpoints p and q. Let G be a bipartite graph with bipartition $(X,Y)$. Define $bn(G)$ to be a maximum integer such that $0\le bn(G)<min\{|X|,|Y|\}$ and (1) for each non-empty subset S of X, if $|S|\le |X|?bn(G)$, then $|N(S)|\ge |S|+bn(G)$, and if $|X|?bn(G)<|S|\le |X|$, then $N(S)=Y$; and (2) for each non-empty subset S of Y, if $|S|\le |Y|?bn(G)$, then $|N(S)|\ge |S|+bn(G)$, and if $|Y|?bn(G)<|S|\le |Y|$, then $N(S)=X$; and (3) $bn(G)=0$ if there is no non-negative integer satisfying (1) and (2).Let G be a bipartite graph with bipartition $(X,Y)$ such that $|X|=|Y|$ and $bn(G)>0$. In this paper, we show that if $\nu (G)\le 2\kappa (G)+4bn(G)?4$, then G is Hamiltonian-laceable; or if $\nu (G)>6bn(G)?2$, then for every pair of vertices $x\in X$ and $y\in Y$, there is an $(x,y)$-path P in G with $|V(P)|\ge 6bn(G)?2$. We show some of its corollaries in k-extendable, bipartite graphs and a conjecture in k-extendable graphs.     

Monochromatic k-edge-connection colorings of graphs

A path in an edge-colored graph $G$ is called monochromatic if any two edges on the path have the same color. For $k\ge 2$, an edge-colored graph $G$ is said to be monochromatic $k$-edge-connected if every two distinct vertices of $G$ are connected by at least $k$ edge-disjoint monochromatic paths, and $G$ is said to be uniformly monochromatic $k$-edge-connected if every two distinct vertices are connected by at least $k$ edge-disjoint monochromatic paths such that all edges of these $k$ paths are colored with a same color. We use $m{c}_k\left(G\right)$ and $um{c}_k\left(G\right)$ to denote the maximum number of colors that ensures $G$ to be monochromatic $k$-edge-connected and, respectively, $G$ to be uniformly monochromatic $k$-edge-connected. In this paper, we first conjecture that for any $k$-edge-connected graph $G$, $m{c}_k\left(G\right)=e\left(G\right)-e\left(H\right)+\lfloor \frac{k}{2}\rfloor$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$. We verify the conjecture for $k=2$. We also prove the conjecture for $G=K_{k+1}$ and $G=K_{k,n}$ with $n\ge k\ge 3$. When $G$ is a minimal $k$-edge-connected graph, we give an upper bound of $m{c}_k\left(G\right)$, i.e., $m{c}_k\left(G\right)\le k-1$. For the uniformly monochromatic $k$-edge-connectivity, we prove that for all $k$, $um{c}_k\left(G\right)=e\left(G\right)-e\left(H\right)+1$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$.     

Finite-Temperature Dimer Method for Finding Saddle Points on Free Energy Surfaces

The dimer method and its variants have been shown to be efficient in finding saddle points on potential surfaces. In the dimer method, the most unstable direction is approximately obtained by minimizing the total potential energy of the dimer. Then, the force in this direction is reversed to move the dimer toward saddle points. When the finite-temperature effect is important for a high-dimensional system, one usually needs to describe the dynamics in a low-dimensional space of reaction coordinates. In this case, transition states are collected as saddle points on the free energy surface. The traditional dimer method cannot be directly employed to find saddle points on a free energy surface since the surface is not known a priori. Here, we develop a finite-temperature dimer method for searching saddle points on the free energy surface. In this method, a constrained rotation dynamics of the dimer system is used to sample dimer directions and an efficient average method is used to obtain a good approximation of the most unstable direction. This approximated direction is then used in reversing the force component and evolving the dimer toward saddle points. Our numerical results suggest that the new method is efficient in finding saddle points on free energy surfaces. © 2019 Wiley Periodicals, Inc.     

Community detection in social networks based on improved Label Propagation Algorithm and balanced link density

Nowadays, community detection has been raised as one of the key research areas in the online social networks mining. One of the most common algorithms in this field is label propagation algorithm (LPA). Even though the LPA method has advantages such as simplicity in understanding and implementation, as well as linear time complexity, it has an important disadvantage of the uncertainty and instability in outcomes, that is, the algorithm detects and reports different combinations of communities in each run. This problem originates from the nature of random selection in the LPA method. In this paper, a novel method is proposed based on the LPA method and the inherent structure, that is, link density feature, of the input network. The proposed method uses a sensitivity parameter (balance parameter); by choosing the appropriate values for it, the desired qualities of the identified communities can be achieved. The proposed method is called Balanced Link Density-based Label Propagation (BLDLP). In comparison with the basic LPA, the proposed method has an advantage of certainty and stability in the output results, whereas its time complexity is still comparable with the basic LPA and of course lowers than many other approaches. The proposed method has been evaluated on real-world known datasets, such as the Facebook social network and American football clubs, and by comparing it with the basic LPA, the effectiveness of the proposed method in terms of the quality of the communities found and the time complexity has been shown.     

Bragg-induced oscillations in non-PT complex photonic lattices

We investigate Bragg-induced oscillations in complex non-PT periodic structures, that is, a periodic medium with gain and loss and not necessarily symmetric under the combined action of parity and time reversal operations. We compare our analytic results based on the expansion of the optical field in Bragg-resonant plane waves with a direct numerical integration of the paraxial wave equation beyond the shallow potential approximation and using a wide Gaussian beam as initial condition. In particular, we study under which conditions a mode trapping phenomenon may still be observed and to inspect how the energy exchange between the spectral modes takes place during propagation in this more general class of asymmetric complex potentials.     

水力劈裂问题的态型近场动力学建模

将态型近场动力学理论引入水力劈裂问题的模拟。构建了能反映岩土类材料准脆性断裂特征的态型近场动力学本构模型,并在物质点间相互作用力模型中加入等效水压力项,以实现在新生裂纹面上跟踪施加水压力。同时,考虑裂纹面间的接触,引入物质点间的短程排斥力作用,并设计了相应的接触算法。通过自编程序将模型和算法应用于含初始裂纹、不含初始裂纹以及含坝基软弱结构面的混凝土重力坝在高水头作用下的水力劈裂过程模拟,并与扩展有限元等模拟结果对比,验证了本文模型和算法的可行性和准确性。     

基于单元破裂的岩石裂纹扩展模拟方法

传统离散元方法在处理破裂问题时, 采用界面上的准则进行判断, 裂纹只能沿着单元边界扩展. 当物理问题存在宏观或微观裂隙时, 在界面上应用准则具有其合理性; 而裂纹沿着单元边界扩展, 使得裂纹路径受网格影响较大, 扩展方向受到限制. 针对上述情况, 可以基于单元破裂的方式, 构建连续- 非连续单元法, 并应用于岩石裂纹扩展问题的模拟. 该方法在连续计算时, 将单元离散为具有物理意义的弹簧系统, 在局部坐标系下由弹簧特征长度、面积求解单元变形和应力, 通过更新局部坐标系和弹簧特征量, 可进一步计算块体大位移、大转动, 连续问题计算结果与有限元一致, 同时提高了计算效率. 在此基础上, 引入最大拉应力与莫尔-库伦的复合准则, 判断单元破裂状态和破裂方向, 并采用局部块体切割的方式, 在单元内形成初始裂纹. 裂纹两侧相应增加新的计算节点, 同时引入内聚力模型描述裂纹两侧的法向、切向作用与张开度及滑移变形之间的关系. 按此方式, 裂纹尖端处的扩展路径可穿过单元内部和单元边界, 在扩展方向的选取上更为准确. 最后, 通过三点弯曲梁、单切口平板拉伸、双切口试样等典型数值试验, 模拟裂纹在拉伸、压剪等各种应力状态下的扩展问题, 并对岩石单轴压缩试验的破坏过程进行模拟, 分析裂纹形成与应力-应变曲线各阶段之间的对应关系. 结果表明: 连续-非连续单元法通过单元内部破裂的方式, 可以显示模拟裂纹萌生、扩展、贯通直至形成宏观裂缝的过程.