Complete graph conjecture for inner-core electrons: homogeneous index case

The complete graph conjecture that encodes the inner-core electrons of atoms with principal quantum number n >or= 2 with complete graphs, and especially with odd complete graphs, is discussed. This conjecture is used to derive new values for the molecular connectivity and pseudoconnectivity basis indices of hydrogen-suppressed chemical pseudographs. For atoms with n = 2 the new values derived with this conjecture are coincident with the old ones. The modeling ability of the new homogeneous basis indices, and of the higher-order terms, is tested and compared with previous modeling studies, which are centered on basis indices that are either based on quantum concepts or partially based on this new conjecture for the inner-core electrons. Two similar algorithms have been proposed with this conjecture, and they parallel the two "quantum" algorithms put forward by molecular connectivity for atoms with n > 2. Nine properties of five classes of compounds have been tested: the molecular polarizabilities of a class of organic compounds, the dipole moment, molar refraction, boiling points, ionization energies, and parachor of a series of halomethanes, the lattice enthalpy of metal halides, the rates of hydrogen abstraction of chlorofluorocarbons, and the pED(50) of phenylalkylamines. The two tested algorithms based on the odd complete graph conjecture give rise to a highly interesting model of the nine properties, and three of them can even be modeled by the same set of basis indices. Interesting is the role of some basis indices all along the model.     

Graph theoretical procedure for obtaining analytical expressions of eigenspectra of linear chains and cycles with alternant vertex weights and same edge weight: Application to some complicated graphs

A graph theoretical procedure for obtaining eigenvalues of linear chains and cycles having alternant vertex weights (h₁, h₂, h₁, h₂, h₁, h₂, …) and the same edge weight (k) have been developed. The eigenvalues of some complicated graphs, such as graphs of linear polyacenes, methylene‐substituted linear polyacenes and cylindrical polyacene strips, stack graphs, and reciprocal graphs have been shown to be generated in closed analytical forms by this procedure. Many such graphs represent chemically important molecules or radicals. © 2005 Wiley Periodicals, Inc. Int J Quantum Chem, 2005     

Improved square coloring of planar graphs

Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that $\frac{3}{2}\mathrm{\Delta }+1$ colors are sufficient to square color every planar graph of maximum degree Δ. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that $2\mathrm{\Delta }+7$ colors are sufficient, which improves the best known bounds when $6?\mathrm{\Delta }?31$.     

The impact of loops on the game of cops and robbers on graphs

In the game of cops and robbers on graphs, the cops and the robber are allowed to pass their turn if they are located on a looped vertex. This paper explores the effect of loops on the cop number and the capture time. We provide examples of graphs where the cop number almost doubles when the loops are removed, graphs where the cop number decreases when the loops are removed, graphs where the capture time is quadratic in the number of vertices and copwin graphs where the cop needs to move away from the robber in optimal play.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

Laplacian spectral characterization of disjoint union of paths and cycles

The Laplacian spectrum of a graph consists of the eigenvalues (together with multiplicities) of the Laplacian matrix. In this article we determine, among the graphs consisting of disjoint unions of paths and cycles, those ones which are determined by the Laplacian spectrum. For the graphs, which are not determined by the Laplacian spectrum, we give the corresponding cospectral non-isomorphic graphs.