Advertisement

In the past ** Boting Yang** has collaborated on articles with

More information about

AbstractIt is known that some triangulation graphs admit straight-line drawings realizing certain characteristics, e.g., greedy triangulation, minimum-weight triangulation, Delaunay triangulation, etc. Lenhart and Liotta (1997) in their pioneering paper on “drawable” minimum-weight triangulations raised an open problem: `Does every triangulation graph whose skeleton is a forest admit a minimum-weight drawing?' In this paper, we answer this problem by disproving it in the general case and even when the skeleton is restricted to a tree or, in particular, a star.

AbstractThe positive semidefinite zero forcing number of a graph is a graph parameter that arises from a non-traditional type of graph colouring and is related to a more conventional version of zero forcing. We establish a relation between the zero forcing and the fast–mixed searching, which implies some NP-completeness results for the zero forcing problem. Relationships between positive semidefinite zero forcing sets and clique coverings are well-understood for chordal graphs. Building upon constructions associated with optimal tree covers and forest covers, we present a linear time algorithm for computing the positive semidefinite zero forcing number of chordal graphs. We also prove that it is NP-complete to determine whether a graph has a positive semidefinite zero forcing set with an additional property.

AbstractGiven a graph that contains an invisible fugitive, the fast searching problem is to find the fast search number, i.e., the minimum number of searchers to capture the fugitive in the fast search model. In this paper, we give a new lower bound on the fast search number. Using the new lower bound, we prove an explicit formula for the fast search number of the Cartesian product of an Eulerian graph and a path. We also give formulas for the fast search number of variants of the Cartesian product. We present an upper bound on the fast search number of hypercubes, and extend the results to a broader class of graphs including toroidal grids.

AbstractLet L be a set of line segments in three dimensional Euclidean space. In this paper, we prove several characterizations of tetrahedralizations. We present an O(mnlogn) algorithm to determine whether L is the edge set of a tetrahedralization, where m is the number of segments and n is the number of distinct endpoints of segments in L. We show that it is NP-complete to decide whether L contains the edge set of a tetrahedralization. We also show that it is NP-complete to decide whether L is a subset of the edge set of a tetrahedralization.

AbstractGiven a graph G=(V,E) in which a fugitive hides on vertices or along edges, graph searching problems are usually to find the minimum number of searchers required to capture the fugitive. In this paper, we consider the problem of finding the minimum number of steps to capture the fugitive. We introduce the fast edge searching problem in the edge search model, which is the problem of finding the minimum number of steps (called the fast edge-search time) to capture the fugitive. We establish relations between the fast edge searching and the fast searching that is the problem of finding the minimum number of searchers to capture the fugitive in the fast search model. While the family of graphs whose fast search number is at most k is not minor-closed for any positive integer k≥2, we show that the family of graphs whose fast edge-search time is at most k is minor-closed. We establish relations between the fast (fast edge) searching and the node searching. These relations allow us to transform the problem of computing node search numbers to the problem of computing fast edge-search numbers or fast search numbers. Using these relations, we prove that the problem of deciding, given a graph G and an integer k, whether the fast (edge-)search number of G is less than or equal to k is NP-complete; and it remains NP-complete for Eulerian graphs. We also prove that the problem of determining whether the fast (edge-)search number of G is half of the number of odd vertices in G is NP-complete; and it remains NP-complete for planar graphs with maximum degree 4. We present a linear time approximation algorithm for the fast edge-search time that always delivers solutions of at most (1+|V|−1|E|+1) times the optimal value. This algorithm also gives us a tight upper bound on the fast search number of graphs. We also show a lower bound on the fast search number using the minimum degree and the number of odd vertices.

AbstractWe consider the zero-visibility cops & robber game restricted to trees. We produce a characterisation of trees of copnumber k and We consider the computational complexity of the zero-visibility Cops and Robber game. We present a heavily modified version of an already-existing algorithm that computes the zero-visibility copnumber of a tree in linear time and we show that the corresponding decision problem is NP-complete on a nontrivial class of graphs.

AbstractPentadiagonal Toeplitz matrices frequently arise in many application areas and have been attracted much attention in recent years. In this paper, we present a numerical algorithm of O(logn) for computing the determinants of general pentadiagonal Toeplitz matrices without imposing any restrictive conditions. In addition, we investigate some special pentadiagonal Toeplitz determinants and their relations to well-known number sequences, and give a few identity formulas for the ordinary Fibonacci sequences and the generalized k-Fibonacci sequences.

AbstractLayered aluminosilicates of PLS-3 were hydrothermally synthesized and employed as the catalysts for the skeletal isomerization of 1-butene. PLS-3 lamellar precursors were successfully prepared at different Si/Al ratios (40–∞) using layered silicate H-kanemite as silica source and tetramethylammonium hydroxide as structure directing agent. A direct calcination caused an interlayer dehydration condensation, converting the precursors into 3-dimensional FER structure with an intersecting micropore system of 8 × 10-membered rings. The physicochemical properties of the Al-PLS-3 materials thus prepared were characterized by various techniques. Their catalytic properties in the skeletal isomerization of 1-butene has been investigated and compared with conventional ferrierite. Al-PLS-3 synthesized at Si/Al = 50 exhibited the same catalytic reactivity as commercial ferrierite. However, possessing smaller crystal size, Al-PLS-3 possessed a much longer catalytic duration against coke formation.

AbstractPLS-4 lamellar precursors, comprised of FER layers and organic structure-directing agent of diethyldimethylammonium cations, were interlayer expanded by silylation with Me2Si(OEt)2 molecules, yielding PLS-4-sil materials with a larger porosity than directly calcined PLS-4 with the CDO topology. The silylation conditions were optimized to obtain a highly ordered interlayer-expanded structure. The silylation introduced about four additional silicon atoms per unit cell to pillar the FER layers. The silicon insertion not only widened the interlayer entrance but also endowed the inorganic zeolite with organic functionality by introducing two methyl groups per silane molecule. As an organic–inorganic hybrid material, PLS-4-sil possessed changeable pore openness and hydrophilicity/hydrophobicity after controlled removal of methyl groups by calcination. Coherently, its adsorption capacities varied with calcination temperature for the adsorption of water, n-hexane and benzene molecules.

Advertisement