Minimum sum set coloring of trees and line graphs of trees

In this paper, we study the minimum sum set coloring (MSSC) problem which consists in assigning a set of x(v) positive integers to each vertex v of a graph so that the intersection of sets assigned to adjacent vertices is empty and the sum of the assigned set of numbers to each vertex of the graph is minimum. The MSSC problem occurs in two versions: non-preemptive and preemptive. We show that the MSSC problem is strongly NP-hard both in the preemptive case on trees and in the non-preemptive case in line graphs of trees. Finally, we give exact parameterized algorithms for these two versions on trees and line graphs of trees.     

Hamiltonian index is NP-complete

In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.     

Triangular line graphs and word sense disambiguation

Linguists often represent the relationships between words in a collection of text as an undirected graph G=(V,E), where V is the vocabulary and vertices are adjacent in G if and only if the words that they represent co-occur in a relevant pattern in the text. Ideally, the words with similar meanings give rise to the vertices of a component of the graph. However, many words have several distinct meanings, preventing components from characterizing distinct semantic fields. This paper examines how the structural properties of triangular line graphs motivate the use of a clustering coefficient on the triangular line graph, thereby helping to identify polysemous words. The triangular line graph of G, denoted by T(G), is the subgraph of the line graph of G where two vertices are adjacent if the corresponding edges in G belong to a K₃.     

A hybrid trust region algorithm for unconstrained optimization

This paper presents a hybrid trust region algorithm for unconstrained optimization problems. It can be regarded as a combination of ODE-based methods, line search and trust region techniques. A feature of the proposed method is that at each iteration, a system of linear equations is solved only once to obtain a trial step. Further, when the trial step is not accepted, the method performs an inexact line search along it instead of resolving a new linear system. Under reasonable assumptions, the algorithm is proven to be globally and superlinearly convergent. Numerical results are also reported that show the efficiency of this proposed method.     

Group connectivity in line graphs

Tutte introduced the theory of nowhere zero flows and showed that a plane graph G has a face k-coloring if and only if G has a nowhere zero A-flow, for any Abelian group A with |A|≥k. In 1992, Jaeger et al. [9] extended nowhere zero flows to group connectivity of graphs: given an orientation D of a graph G, if for any b:V(G)?A with ∑_v∈V(G)b(v)=0, there always exists a map f:E(G)?A−{0}, such that at each v∈V(G), in A, then G is A-connected. Let Z₃ denote the cyclic group of order 3. In [9], Jaeger et al. (1992) conjectured that every 5-edge-connected graph is Z₃-connected. In this paper, we proved the following.

• (i) 

  Every 5-edge-connected graph is Z3-connected if and only if every 5-edge-connected line graph is Z3-connected.

• (ii) 

  Every 6-edge-connected triangular line graph is Z3-connected.

• (iii) 

  Every 7-edge-connected triangular claw-free graph is Z3-connected.

In particular, every 6-edge-connected triangular line graph and every 7-edge-connected triangular claw-free graph have a nowhere zero 3-flow.     

Freeness for 13 lines arrangements is combinatorial

We prove Terao conjecture saying that the freeness is determined by the combinatorics for arrangements of 13 lines in the complex projective plane.     

Helium- and argon-broadening coefficients of phosphine lines in the ν2 and ν4 bands

Pressure broadening of phosphine lines by helium and argon at room temperature has been experimentally investigated by high-resolution diode-laser spectroscopy. The broadening coefficients are measured for 38 transitions of PH₃ in the ^QR branch of the ν₂ band and in the ^PP and ^RP branches of the ν₄ band. The recorded lines with J values ranging from 3 to 14 and K from 0 to 10 are located between 1062 and 1094 cm⁻¹. The retrieval of the collisional widths is carried out by fitting each spectral line with a Voigt profile, a Rautian profile and a speed-dependent Rautian profile. The latter model provides larger broadening coefficients than the Voigt model. They are also calculated on the basis of a semiclassical model involving the atom-atom Lennard-Jones potential. The theoretical results are in reasonable agreement with the experimental data and reproduce the J and K dependencies of the broadenings.     

CO_2激光边带光谱仪用于SF_6分子v_3带Q支吸收谱的研究

用绝对频率精度优于1.2MHz的CO_2激光边带光谱仪记录了SF_6分子v_3带Q支的多普勒受限吸收谱,光谱范围在CO_2激光10P(16)支线中心两侧,距支线中心8.0～12.4 GHz。用内插法以<6MHz的均方误差测量了百余条跃迁谱线的频率,并标识出Q_Z、Q_R、Q_X、Q_W、Q_A等亚支的谱线,量子数J从26到83。用最小二乘法拟合实验数据得到了v_3带的部分光谱常数。     

Thermodynamics of solid surfaces

In contrast to the thermodynamics of fluid surfaces, the thermodynamics of solid surfaces was not elaborated in detail by Gibbs and other founders of surface thermodynamics. During recent decades, significant progress in this field has been achieved in both the understanding of old notions, like chemical potentials, and in formulating new areas. Applying to solid surfaces, basic relationships of classical theory of capillarity, such as the Laplace equation, the Young equation, the Gibbs adsorption equation, the Gibbs-Curie principle, the Wulff theorem and the Dupré rule, were reformulated and generalized. The thermodynamics of self-dispersion of solids and the thermodynamics of contact line phenomena were developed as well. This review provides a fresh insight into the modern state of the thermodynamics of solid surfaces. Not only a solid surface itself, both in a macroscopic body and in the system of fine particles, but also the interaction of solid surfaces with fluid phases, such as wetting phenomenon, will be analyzed. As the development of surface thermodynamics has given a powerful impetus to the creation of new experimental methods, some of these will be described as examples.     

关于带有完全对称函数的广义数值域

本文给出了矩阵Ａ的带有完全对称函数Ｃｋ的ｍ－数值域在复平面上为线段的充分必要条件．