On subspectral problem—benzenoid hydrocarbons with common eigenvalues ±1

Summary The method for the contraction and expansion of graphs is used to treat the subspectrality of benzenoid hydrocarbons in relation to eigenvalues ±1. Counts of benzenoid hydrocarbons together with degeneracies of eigenvalues have been carried out for all species having h 7 hexagons. In addition, twelve homologous series are evaluated, and the closed results for the distribution of eigenvalues ± 1 and degeneracies in terms of the number of repeated units are tabulated. This method is universal and applicable to cases sharing other eigenvalues and to nonbenzenoid systems.Also known as Yuan-sun Kiang     

Combinatorial Clar sextet theory

Clar structures recently used as basis-set to compute resonance energies [9] are identified as maximal independent sets of benzenoid hydrocarbons colored in a special way. Binomial properties of such objects are induced for several catafusenes and perifusenes (Eqs. 2–31). Novel polynomials, called Clar polynomials, are given for perifusens in terms of units of catafusenes which allow display and enumeration of the populations of their Clar structures. The work is particularly pertinent to that of [8] and [9].This paper is dedicated to Professor Eric Clar; the Doyen of aromatic chemistry.     

The spum and sum-diameter of graphs: Labelings of sum graphs

A sum graph is a finite simple graph whose vertex set is labeled with distinct positive integers such that two vertices are adjacent if and only if the sum of their labels is itself another label. The spum of a graph G is the minimum difference between the largest and smallest labels in a sum graph consisting of G and the minimum number of additional isolated vertices necessary so that a sum graph labeling exists. We investigate the spum of various families of graphs, namely cycles, paths, and matchings. We introduce the sum-diameter, a modification of the definition of spum that omits the requirement that the number of additional isolated vertices in the sum graph is minimal, which we believe is a more natural quantity to study. We then provide asymptotically tight general bounds on both sides for the sum-diameter, and study its behavior under numerous binary graph operations as well as vertex and edge operations. Finally, we generalize the sum-diameter to hypergraphs.     

Feature generation based on relation learning and image partition for occluded person re-identification

In order to solve the challenging tasks of person re-identification(Re-ID) in occluded scenarios, we propose a novel approach which divides local units by forming high-level semantic information of pedestrians and generates features of occluded parts. The approach uses CNN and pose estimation to extract the feature map and key points, and a graph convolutional network to learn the relation of key points. Specifically, we design a Generating Local Part (GLP) module to divide the feature map into different units. Based on different occluded conditions, the partition mode of GLP has high flexibility and variability. The features of the non-occluded parts are clustered into an intermediate node, and then the spatially correlated features of the occluded parts are generated according to the de-clustering operation. We conduct experiments on both the occluded and the holistic datasets to demonstrate its effectiveness.     

Single image shadow detection via uncertainty analysis and GCN-based refinement strategy

Learning-based shadow detection methods have achieved an impressive performance, while these works still struggle on complex scenes, especially ambiguous soft shadows. To tackle this issue, this work proposes an efficient shadow detection network (ESDNet) and then applies uncertainty analysis and graph convolutional networks for detection refinement. Specifically, we first aggregate global information from high-level features and harvest shadow details in low-level features for obtaining an initial prediction. Secondly, we analyze the uncertainty of our ESDNet for an input shadow image and then take its intensity, expectation, and entropy into account to formulate a semi-supervised graph learning problem. Finally, we solve this problem by training a graph convolution network to obtain the refined detection result for every training image. To evaluate our method, we conduct extensive experiments on several benchmark datasets, i.e., SBU, UCF, ISTD, and even on soft shadow scenes. Experimental results demonstrate that our strategy can improve shadow detection performance by suppressing the uncertainties of false positive and false negative regions, achieving state-of-the-art results.     

Efficient graph attentional network for 3D object detection from Frustum-based LiDAR point clouds

LiDAR-based 3D object detection is important for autonomous driving scene perception, but point clouds produced by LiDAR are irregular and unstructured in nature, and cannot be adopted by the conventional Convolutional Neural Networks (CNN). Recently, Graph Convolutional Networks (GCN) has been proved as an ideal way to handle non-Euclidean structure data, as well as for point cloud processing. However, GCN involves massive computation for searching adjacent nodes, and the heavy computational cost limits its applications in processing large-scale LiDAR point cloud in autonomous driving. In this work, we adopt a frustum-based point cloud-image fusion scheme to reduce the amount of LiDAR point clouds, thus making the GCN-based large-scale LiDAR point clouds feature learning feasible. On this basis, we propose an efficient graph attentional network to accomplish the goal of 3D object detection in autonomous driving, which can learn features from raw LiDAR point cloud directly without any conversions. We evaluate the model on the public KITTI benchmark dataset, the 3D detection mAP is 63.72% on KITTI Cars, Pedestrian and Cyclists, and the inference speed achieves 7.9 fps on a single GPU, which is faster than other methods of the same type.     

Reaction graphs and a construction of reaction networks

Summary A general definition of reaction graphs is presented. For a pair of isomeric molecular graphs and , related by a chemical transformation , the reaction graph is determined using a maximal common subgraph defined for vertex mapping . A binary operation defined for graphs constructed over the same vertex set enables us to decompose the reaction graph into the sum of prototype reaction graphs. A decomposition of an overall reaction graph can be advantageously used for the construction of a reaction network. An oriented path in this network beginning at and ending at corresponds to a breakdown of the transformation into a sequence of intermediates.     

Chemical applications of topology and group theory

The 60 even permutations of the ligands in the five-coordinate complexes, ML ₅, form the alternating group A ₅, which is isomorphic with the icosahedral pure rotation group I. Using this idea, it is shown how a regular icosahedron can be used as a topological representation for isomerizations of the five-coordinate complexes, ML ₅, involving only even permutations if the five ligands L correspond either to the five nested octahedra with vertices located at the midpoints of the 30 edges of the icosahedron or to the five regular tetrahedra with vertices located at the midpoints of the 20 faces of the icosahedron. However, the 120 total permutations of the ligands in five-coordinate complexes ML ₅ cannot be analogously represented by operations in the full icosahedral point group I _h, since I _his the direct product I×C₂ whereas the symmetric group S ₅ is only the semi-direct product A ₅S₂. In connection with previously used topological representations on isomerism in five-coordinate complexes, it is noted that the automorphism groups of the Petersen graph and the Desargues-Levi graph are isomorphic to the symmetric group S ₅ and to the direct product S ₅×S ₂, respectively. Applications to various fields of chemistry are briefly outlined.     

图的顶点着色问题的DNA算法

图的顶点着色问题是指无向图中任意两个相邻顶点都分配到不同的颜色,这个问题是著名的NP-完全问题,没有非常有效的算法.但在1994年Adleman^[1]首次提出用DNA计算解决NP-完全问题,设计出一种全新的计算模式—模拟生物分子DNA的结构并借助于分子生物技术进行计算,使得NP-完全问题的求解可能得到解决.本文首先提出了基于分子生物技术的图的顶点着色问题的DNA算法,算法的关键是对图中的顶点和顶点的颜色进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离,依据分子生物学的实验方法,本文提出的算法是有效和可行的;其次指出了该算法的优点、存在的问题及将来进一步的研究方向.     

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$.