On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

三维位势问题的梯度边界积分方程的新解法

三维位势问题的边界元分析中,关于坐标变量的边界位势梯度的计算是一个困难的问题. 已有一些方法着手解决这个问题,然而,这些方法需要复杂的理论推导和大量的数值计算. 本文提出求解一般边界位势梯度边界积分方程的辅助边值问题法. 该方法构造了与原边界值问题具有相同解域的辅助边值问题,该辅助边值问题具有已知解,因此通过求解此辅助边值问题,可获得梯度边界积分方程对应的系统矩阵,然后将此系统矩阵应用于求解原边值问题,求解过程非常简单,只需求解一个线性系统即可获得原边值问题的解. 值得注意的是,在求解原边值问题时,不再需要重新计算系统矩阵,因此辅助边值问题法的效率并不很差. 辅助边值问题法避免了强奇异积分的计算,具有数学理论简单、程序设计容易、计算精度高等优点,为坐标变量梯度边界积分方程的求解提供了一个新的途径. 3个标准的数值算例验证了方法的有效性.      

Finding any given 2‐factor in sparse pseudorandom graphs efficiently

Given an $n$‐vertex pseudorandom graph $G$ and an $n$‐vertex graph $H$ with maximum degree at most two, we wish to find a copy of $H$ in $G$, that is, an embedding $\phi :V\left(H\right)\to V\left(G\right)$ so that $\phi \left(u\right)\phi \left(v\right)\in E\left(G\right)$ for all $uv\in E\left(H\right)$. Particular instances of this problem include finding a triangle‐factor and finding a Hamilton cycle in $G$. Here, we provide a deterministic polynomial time algorithm that finds a given $H$ in any suitably pseudorandom graph $G$. The pseudorandom graphs we consider are $\left(p,\lambda \right)$‐bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, $\mathrm{\Omega }\left(pn\right)$. A $\left(p,\lambda \right)$‐bijumbled graph is characterised through the discrepancy property: $|e\left(A,B\right)?p|A||B||<\lambda \sqrt{|A||B|}$ for any two sets of vertices $A$ and $B$. Our condition $\lambda =O(p^{2}n/\log n)$ on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption‐reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications.     

Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property

A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs.     

Cycloparaphenylene (CPP) series are molecular models for graphene armchair edges: trends in their aromaticity and cyclic conjugation are evaluated

Cycloparaphenylene ([r]CPP) and cyclacene ([r]CA) series are models for short carbon nanotubes. It is shown that armchair edges in model cycloparaphenylenes possess greater aromaticity and cyclic conjugation than do zigzag edges in model cyclacenes. According to Aihara’s bond resonance energy (BRE) and Bosanac and Gutman energy effect (ef) measurements, cycloparaphenylenes are twice as aromatic as cyclacenes. The general solution of all eigenvalues of all members of the cycloparaphenylene series is given. The origin of the recurrence of some eigenvalues are determined.