Search

We conjecture that all connected graphs of order n have von Neumann entropy at least as great as the star K 1 , n − 1 and prove this for almost all graphs of order n . We show that connected graphs of order n have Rényi 2-entropy at least as great as K 1 , n − 1 and for α > 1 , K n maximizes Rényi α -entropy over graphs of order n . We show that adding an edge to a graph can lower its von Neumann entropy. [ABSTRACT FROM AUTHOR]

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: We study a robustness model for the minimum coloring problem, where any vertex of the input-graph has some presence probability . We show that, under this model, the original coloring problem gives rise to a new coloring version (called Probabilistic Min Coloring) where the objective becomes to determine a partition of into independent sets , that minimizes the quantity , where, for any independent set , . We show that Probabilistic Min Coloring is NP-hard and design a polynomial time approximation algorithm achieving non-trivial approximation ratio. We then focus ourselves on probabilistic coloring of bipartite graphs and show that the problem of determining the best k-coloring (called Probabilistic Min -Coloring) is NP-hard, for any . We finally study Probabilistic Min Coloring and Probabilistic Min -Coloring in a particular family of bipartite graphs that plays a crucial role in the proof of the NP-hardness result just mentioned, and in complements of bipartite graphs. [Copyright &y& Elsevier]

Abstract: A framework is a straight line realization of a graph in , given by a map . We prove that if is an infinitesimally rigid framework then there is an infinitesimally rigid framework for which the points , , are distinct points of the grid, where . We also show that such a framework on G can be constructed in time. [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]

It is known that the independence number of a connected claw-free graph G of order n is at most (n+1)/2. We improve this result by showing that this bound still holds for the upper irredundance number IR(G). We characterize the connected claw-free graphs for which IR(G)=(n+1)/2 and give some properties of those graphs for which IR(G)=n/2 if n is even or IR(G)=(n−1)/2 if n is odd. [Copyright &y& Elsevier]