A subset S of vertices in a graph G is a secure dominating set of G if S is a dominating set of G and, for each vertex u⁄∈S, there is a vertex v∈S such that uv is an edge and (S∖{v})∪{u} is also a dominating set of G. The secure domination number of G, denoted by γs(G), is the cardinality of a smallest secure dominating sets of G. In this paper, we prove that, for any outerplanar graph with n≥4 vertices, γs(G)≥(n+4)/5 and the bound is tight.

A subset S of vertices of G is a total dominating set if, for any vertex v, there is a vertex in S adjacent to v. A total dominating set S is a secure total dominating set if, for any vertex v∉S, there is a vertex u∈S such that uv is an edge and (S∖{u})∪{v} is also a total dominating set. In this paper, we design an O(m)-time algorithm for computing a minimum secure total dominating set in a proper interval graph, where m is the number of edges.

Abstract Suppose thatG(V0∪V1,E) is a bipartite graph with partite sets of equal size.Gis calledhyper hamiltonian laceableif (1) it has a hamiltonian path between any pair of vertices in different partite sets, and (2) for any vertexv∈Vi, there is a hamiltonian path inG−vbetween any two vertices inV1 −i. Star and bubble‐sort graphs have been considered as interconnection networks for parallel and distributed systems, and these graphs are known to be hyper hamiltonian laceable. Furthermore, it is well known that these graphs belong to the class of Cayley graphs on symmetric groups generated by a set of transpositions. In this article, we generalize those results by showing that any Cayley graph generated by transpositions is hyper hamiltonian laceable. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(3), 121–124 2006

We introduce a new model for diagnosable systems called (t, k)-diagnosable system which guarantees that at least k faulty units (processors) in a system are detected provided that the number of faulty units does not exceed t. This system includes classical one-step diagnosable systems and sequentially diagnosable systems. We prove a necessary and sufficient condition for (t, k)-diagnosable system, and discuss a lower bound for diagnosability. Finally, we deal with a relation between (t, k)-diagnosability and diagnosability of classical basic models.