P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi, in Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004), 157–177, and T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, in Global defensive alliances in graphs, Electron. J. Combin. 10 (2003), introduced the defensive alliance number $a\left(G\right)$, strong defensive alliance number $\widehat{a}\left(G\right)$, and global defensive alliance number ${\gamma }_a\left(G\right)$. In this paper, we consider relationships between these parameters and the domination number $\gamma \left(G\right)$. For any positive integers...

If a graph is connected then the largest eigenvalue (i.e., index) generally changes (decreases or increases) if some local modifications are performed. In this paper two types of modifications are considered: (i) for a fixed vertex, t edges incident with it are deleted, while s new edges incident with it are inserted; (ii) for two non-adjacent vertices, t edges incident with one vertex are deleted, while s new edges incident with the other vertex are inserted. ...

A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. In this paper, we obtain bounds for the b- chromatic number of induced subgraphs in terms of the b-chromatic number of the original graph. This turns out to be a generalization...

Let $G$ be a simple connected graph of order $n$ with degree sequence $(d_1,d_2,...,d_n)$. Denote ${{(}^{\alpha }t)}_i={\sum }_{j:i\sim j}{d}_j^{\alpha }$, ${{(}^{\alpha }m)}_i={{(}^{\alpha }t)}_i/d_i^{\alpha }$ and ${{(}^{\alpha }N)}_i={\sum }_{j:i\sim j}{{(}^{\alpha }t)}_j$, where $\alpha$ is a real number. Denote by ${\lambda }_1\left(G\right)$ and ${\mu }_1\left(G\right)$ the spectral radius of the adjacency matrix and the Laplacian matrix of $G$, respectively. In this paper, we present some upper and lower bounds of ${\lambda }_1\left(G\right)$ and ${\mu }_1\left(G\right)$ in terms of ${{(}^{\alpha }t)}_i$, ${{(}^{\alpha }m)}_i$ and ${{(}^{\alpha }N)}_i$. Furthermore, we also characterize some extreme graphs which attain these upper bounds. These results theoretically improve and generalize some known results.

Let $G$ be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that $G$ admits a bipartition such that each vertex class meets edges of total weight at least $(w_1-{\Delta }_1)/2+2w_2/3$, where $w_i$ is the total weight of edges of size $i$ and ${\Delta }_1$ is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph $G$ (i.e., multi-hypergraph), we show that there exists a bipartition of $G$ such that each vertex class meets edges of total weight at least $(w_0-1)/6+(w_1-{\Delta }_1)/3+2w_2/3$, where $w_0$ is the number...

An edge-coloured graph G is rainbow-connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow-connected. In this paper we show some new bounds for the rainbow connection number of graphs depending on the minimum degree and other graph parameters. Moreover, we discuss sharpness of some of these bounds.

This article presents a basic scheme for deriving systematically a filtering algorithm from the graph properties based representation of global constraints. This scheme is based on the bounds of the graph parameters used in the description of a global constraint. The article provides bounds for the most common used graph parameters.

This article presents a basic scheme for deriving systematically a filtering algorithm from the graph properties based representation of global constraints. This scheme is based on the bounds of the graph parameters used in the description of a global constraint. The article provides bounds for the most common used graph parameters.

If $G$ is a graph, an open Hamiltonian walk is any open sequence of edges of minimal length which includes every vertex of $G$. In this paper bounds of lengths of open Hamiltonian walks are studied.

Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for trees, and we relate them to the known bounds on the minimum cardinality of global...

A total dominating set in a graph $G$ is a subset $X$ of $V\left(G\right)$ such that each vertex of $V\left(G\right)$ is adjacent to at least one vertex of $X$. The total domination number of $G$ is the minimum cardinality of a total dominating set. A function $f:V\left(G\right)\to \{-1,1\}$ is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of $G$ is the minimum weight of an SDF on $G$. In this paper...