Search

Abstract: The bandwidth of a graph G is the minimum of the quantity taken over all proper numberings f of G. The strong product of two graphs G and H, written as , is the graph with vertex set and with adjacent to if one of the following holds: (a) and are adjacent to and in G and H, respectively, (b) is adjacent to in G and , or (c) and is adjacent to in H. In this paper, we investigate the bandwidth of the strong product of two connected graphs. Let G be a connected graph. We denote the diameter of G by . Let d be a positive integer and let be two vertices of G. Let denote the set of vertices so that the distance between x and in G is at most d. We define as the minimum value of over all vertices x of G. Let denote the set of vertices z such that the distance between x and z in G is at most and z is adjacent to y. We denote the larger of and by . We define if G is complete and as the minimum of over all pair of vertices of G otherwise. Let G and H be two connected graphs. Among other results, we prove that if and , then . Moreover, we show that this result determines the bandwidth of the strong product of some classes of graphs. Furthermore, we study the bandwidth of the strong product of power of paths with complete bipartite graphs. [Copyright &y& Elsevier]

Abstract: Assume that is an undirected graph, and . For every , we denote by the set of all elements of C that are within distance one from . If all the sets for are non-empty, and pairwise different, then C is called a locating-dominating set. The smallest possible density of a locating-dominating set in the infinite triangular grid is shown to be . [Copyright &y& Elsevier]

Abstract: In this version of the Cops and Robber game, the cops move in tandems, or pairs, such that they are at distance at most one after every move. We present a recognition theorem for tandem-win graphs, and a characterization of triangle-free tandem-win graphs. [Copyright &y& Elsevier]

Abstract: This paper establishes a necessary and sufficient condition for a CO-irredundant set of vertices of a graph to be maximal and shows that the smallest cardinality of a maximal CO-irredundant set in an n vertex graph with maximum degree is bounded below by for , for and for . This result is best possible and extremal graphs are characterised for . [Copyright &y& Elsevier]

We show that, if NP≠ZPP, for any ϵ>0, the toughness of a graph with n vertices is not approximable in polynomial time within a factor of 1/2(n/2)1−ϵ. We give a 4-approximation for graphs with toughness bounded by 1/3 (n/2)1−ϵ. We give a 4-approximation for graphs with toughness bounded by 1/3 and we show that this result cannot be generalized to graphs with a bounded toughness. More exactly we prove that there is no constant approximation for graphs with bounded toughness, unless P=NP. [Copyright &y& Elsevier]

We consider two problems related to the cycle double cover (CDC) conjecture for graphs: the oriented perfect path double cover (OPPDC) and the oriented faithful cycle cover. While we characterize the latter the OPPDC is an interesting open problem. [Copyright &y& Elsevier]

Let p be a prime. It was shown by Folkman (J. Combin. Theory 3 (1967) 215) that a regular edge-transitive graph of order 2p or 2p2 is necessarily vertex-transitive. In this paper an extension of his result in the case of cubic graphs is given. It is proved that, with the exception of the Gray graph on 54 vertices, every cubic edge-transitive graph of order 2p3 is vertex-transitive. [Copyright &y& Elsevier]