On traceable iterated line graph and hamiltonian path index

Xiong and Liu[21]gave a characterization of the graphs G for which the n-iterated line graph L^(n)(G)is hamiltonian,for n≥2.In this paper,we study the existence of a hamiltonian path in L^(n)(G),and give a characterization of G for which L^(n)(G)has a hamiltonian path.As applications,we use this characterization to give several upper bounds on the hamiltonian path index of a graph.

DISCUSSION ON MINIMUM FLOW MODEL FOR ITS RELATIONSHIP WITH HAMILTONIAN PATH PROBLEM

A negative example shows that the model given by Mason Iri is used to prove that the relationship between the minimum flow problem and the Hamiltonian path problem in a (directed) network, is not rigorous. A new model called minimum spanning flow in a network is established to revise the old one. It is proved that the problem of determining whether there is a Hamiltonian path from a specified vertex s to another t on a given digraph can be reducible at polynomial time to the problem of constructing a minimum spanning flow in a two-terminal extended network s,t , with the unit capacity for all arcs.

Classes of tree-based networks

Recently,so-called tree-based phylogenetic networks have attracted considerable attention.These networks can be constructed from a phylogenetic tree,called the base tree,by adding additional edges.The primary aim of this study is to provide sufficient criteria for tree-basedness by reducing phylogenetic networks to related graph structures.Even though it is generally known that determining whether a network is tree-based is an NP-complete problem,one of these criteria,namely edge-basedness,can be verified in linear time.Surprisingly,the class of edgebased networks is closely related to a well-known family of graphs,namely,the class of generalized series-parallel graphs,and we explore this relationship in full detail.Additionally,we introduce further classes of tree-based networks and analyze their relationships.

Cognitive Supervisor for an Autonomous Swarm of Robots

As a sequel to our recent work [1], in which a control framework was developed for large-scale joint swarms of unmanned ground (UGV) and aerial (UAV) vehicles, the present paper proposes cognitive and meta-cognitive supervisor models for this kind of distributed robotic system. The cognitive supervisor model is a formalization of the recently Nobel-awarded research in brain science on mammalian and human path integration and navigation, performed by the hippocampus. This is formalized here as an adaptive Hamiltonian path integral, and efficiently simulated for implementation on robotic vehicles as a pair of coupled nonlinear Schr?dinger equations. The meta-cognitive supervisor model is a modal logic of actions and plans that hinges on a weak causality relation that specifies when atoms may change their values without specifying that they must change. This relatively simple logic is decidable yet sufficiently expressive to support the level of inference needed in our application. The atoms and action primitives of the logic framework also provide a straight-forward way of connecting the meta-cognitive supervisor with the cognitive supervisor, with other modules, and to the meta-cognitive supervisors of other robotic platforms in the swarm.

Fault-tolerant hamiltonian cycles and paths embedding into locally exchanged twisted cubes

The foundation of information society is computer interconnection network,and the key of information exchange is communication algorithm.Finding interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and protocols.Nowadays,people can build complex interconnection networks by using very large scale integration(VLSI)technology.Locally exchanged twisted cubes,denoted by(s+t+1)-dimensional LeTQ_(s,t) which combines the merits of the exchanged hypercube and the locally twisted cube.It has been proved that the LeTQ_(s,t) has many excellent properties for interconnection networks,such as fewer edges,lower overhead and smaller diameter.Embeddability is an important indicator to measure the performance of interconnection networks.We mainly study the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube,LeTQ_(s,t)-(f_(v)+f_(e)),with faulty vertices f_(v) and faulty edges fe.Firstly,we prove that an LeTQ_(s,t) can tolerate up to s-1 faulty vertices and edges when embedding a Hamiltonian cycle,for s≥2,t≥3,and s≤t.Furthermore,we also prove another result that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQ_(s,t) with up to(s-2)faulty vertices and edges.That is,we show that LeTQ_(s,t) is(s-1)-Hamiltonian and(s-2)-Hamiltonian-connected.The results are proved to be optimal in this paper with at most(s-1)-fault-tolerant Hamiltonicity and(s-2)fault-tolerant Hamiltonian connectivity of LeTQ_(s,t).

Note on the Longest Paths in {K_(1,4),K_(1,4)+e}-free Graphs

A graph G is{K_(1,4),K_(1,4)+e}-free if G contains no induced subgraph isomorphic to K_(1,4) or KI,a+e In this paper,we show that G has a path which is either hamiltonian or of length at least 25(G)+2 if G is a connected{K_(1,4),K_(1,4)+e}-free graph on at least 7 vertices.

An Implicit Degree Condition for Relative Length of Long Paths and Cycles in Graphs

For a graph G, we denote by p（G） and c（G） the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id（v） denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n ＋ 1, then either G contains a hamiltonian path, or c（G） 〉 p（G） - 1.

redPATH:Reconstructing the Pseudo Development Time of Cell Lineages in Single-cell RNA-seq Data and Applications in Cancer

The recent advancement of single-cell RNA sequencing(scRNA-seq)technologies facilitates the study of cell lineages in developmental processes and cancer.In this study,we developed a computational method,called redPATH,to reconstruct the pseudo developmental time of cell lineages using a consensus asymmetric Hamiltonian path algorithm.Besides,we developed a novel approach to visualize the trajectory development and implemented visualization methods to provide biological insights.We validated the performance of redPATH by segmenting different stages of cell development on multiple neural stem cell and cancer datasets,as well as other single-cell transcriptome data.In particular,we identified a stem cell-like subpopulation in malignant glioma cells.These cells express known proliferative markers,such as GFAP,ATP1A2,IGFBPL1,and ALDOC,and remain silenced for quiescent markers such as ID3.Furthermore,we identified MCL1 as a significant gene that regulates cell apoptosis and CSF1R for reprogramming macrophages to control tumor growth.In conclusion,redPATH is a comprehensive tool for analyzing scRNA-seq datasets along the pseudo developmental time.redPATH is available at https://github.com/tinglabs/redPATH.

An optical fiber network oracle for NP-complete problems

The modern information society is enabled by photonic fiber networks characterized by huge coverage and great complexity and ranging in size from transcontinental submarine telecommunication cables to fiber to the home and local segments.This world-wide network has yet to match the complexity of the human brain,which contains a hundred billion neurons,each with thousands of synaptic connections on average.However,it already exceeds the complexity of brains from primitive organisms,i.e.,the honey bee,which has a brain containing approximately one million neurons.In this study,we present a discussion of the computing potential of optical networks as information carriers.Using a simple fiber network,we provide a proof-of-principle demonstration that this network can be treated as an optical oracle for the Hamiltonian path problem,the famous mathematical complexity problem of finding whether a set of towns can be travelled via a path in which each town is visited only once.Pronouncement of a Hamiltonian path is achieved by monitoring the delay of an optical pulse that interrogates the network,and this delay will be equal to the sum of the travel times needed to visit all of the nodes(towns).We argue that the optical oracle could solve this NP-complete problem hundreds of times faster than brute-force computing.Additionally,we discuss secure communication applications for the optical oracle and propose possible implementation in silicon photonics and plasmonic networks.

Infinite Circulant Digraphs and Random Infinite Circulant Digraphs

In this paper, we completely determine the connectivity of every infinite circulant digraphs and prove that almost all infinite circulant digraphs are infinitely strongly connected and therefore have both one-and two-way infinite Hamiltonian paths.

A Problem in Combinatorics

In this paper, by using a novel method of graph-colouring, we give a solution for a Hamiltonian Path of a graph.

Edge-Fault-Tolerant Properties of Augmented Cubes

As an enhancement on the hypercube Qn, the augmented cube AQn, pro- posed by Choudum and Sunitha [Choudum S.A., Sunitha V., Augmented cubes, Networks, 40（2）（2002）, 71-84], possesses some properties superior to the hypercube Qn. In this paper, assuming that （u, v） is an arbitrary fault-free d-link in an n-dimensional augmented cubes, 1 ≤ d ≤ n - 1, n ≥ 4. We show that there exists a fault-free Hamiltonian cycle in the augmented cube contained （u, v）, even if there are 2n - 3 link faults.