International Journal of Foundations of Computer Science

For an optimization problem known to be NP-Hard, the dichotomy study investigates the reduction instances to determine the line separating polynomial-time solvable vs NP-Hard instances (easy vs hard instances). In this paper, we investigate the well-studied Hamiltonian cycle problem (HCYCLE), and present an interesting dichotomy result on split graphs. T. Akiyama et al. (1980) have shown that HCYCLE is NP-complete on planar bipartite graphs with maximum degree $3$. We use this result to show that HCYCLE is NP-complete for $K_{1,5}$-free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in $K_{1,3}$-free and $K_{1,4}$-free split graphs. We believe that the structural results presented in this paper can be used to show similar dichotomy result for Hamiltonian path problem and other variants of Hamiltonian cycle (path) problems.

The Cayley graph generated by a transposition tree ${\mathrm{\Gamma }}_n$ is a class of Cayley graphs that contains the star graph and the bubble sort graph. A graph $G$ is called strongly Menger (SM for short) (edge) connected if each pair of vertices $x,y$ are connected by $min\{d_G(x),d_G(y)\}$ (edge)-disjoint paths, where $d_G(x),d_G(y)$ are the degree of $x$ and $y$ respectively. In this paper, the maximally edge-fault-tolerant and the maximally vertex-fault-tolerant of ${\mathrm{\Gamma }}_n$ with respect to the SM-property are found and thus generalize or improve the results in [19, 20, 22, 26] on this topic.

We study ultimate periodicity properties related to overlaps between the suffixes of a left-infinite word $\lambda$ and the prefixes of a right-infinite word $\rho$. The main theorem states that the set of minimum lengths of words $x$ and $x^{\prime }$ such that $x{\lambda }_n={\rho }_n{x}^{\prime }$ or ${\lambda }_{n}x=x^{\prime }{\rho }_n$ is finite, where $n$ runs over positive integers and ${\lambda }_n$ and ${\rho }_n$ are respectively the suffix of $\lambda$ and the prefix of $\rho$ of length $n$, if and only if $\lambda$ and $\rho$ are ultimately periodic words of the form $\lambda =u^{-\infty }v$ and $\rho ={wu}^{\infty }$ for some finite words $u$, $v$ and $w$.

Given a complete graph $G=(V,E)$, with nonnegative edge costs, two subsets $R\subset V$ and $R^{\prime }\subset R$, a partition ${ℛ}=\{R_1,R_2,\dots ,R_k\}$ of $R$, $R_i\cap R_j=\varphi$, $i\ne j$ and ${{ℛ}}^{\prime }=\{R_1^{\prime },R_2^{\prime },\dots ,R_k^{\prime }\}$ of $R^{\prime }$, $R_i^{\prime }\subset R_i$, a clustered Steiner tree is a tree $T$ of $G$ that spans all vertices in $R$ such that $T$ can be cut into $k$ subtrees $T_i$ by removing $k-1$ edges and each subtree $T_i$ spans all vertices in $R_i$, $1\le i\le k$. The cost of a clustered Steiner tree is defined to be the sum of the costs of all its edges. A clustered selected-internal Steiner tree of $G$ is a clustered Steiner tree for $R$ if all vertices in $R_i^{\prime }$ are internal vertices of $T_i$. The clustered selected-internal Steiner tree problem is concerned with the determination of a clustered selected-internal Steiner tree $T$ for $R$ and $R^{\prime }$ in $G$ with minimum cost. In this paper, we present the first known approximation algorithm with performance ratio $(\rho +4)$ for the clustered selected-internal Steiner tree problem, where $\rho$ is the best-known performance ratio for the Steiner tree problem.

The processor failures in a multiprocessor system have a negative impact on its distributed computing efficiency. Because of the rapid expansion of multiprocessor systems, the importance of fault diagnosis is becoming increasingly prominent. The $h$-component diagnosability of $G$, denoted by $c{t}_h(G)$, is the maximum number of nodes of the faulty set $F$ that is correctly identified in a system, and the number of components in $G-F$ is at least $h$. In this paper, we determine the $(h+1)$-component diagnosability of general networks under the PMC model and MM${}^{\ast }$ model. As applications, the component diagnosability is explored for some well-known networks, including complete cubic networks, hierarchical cubic networks, generalized exchanged hypercubes, dual-cube-like networks, hierarchical hypercubes, Cayley graphs generated by transposition trees (except star graphs), and DQcube as well. Furthermore, we provide some comparison results between the component diagnosability and other fault diagnosabilities.