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...

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, [...] γtd(G) ${\gamma }_t^d\left(G\right)$ , is the minimum cardinality of such a set. We observe that [...] γtd(G)≤γt(G)...

Let G = (V(G),E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆ V(G) is called a global offensive k-alliance if |N(v)∩S| ≥ |N(v)-S|+k for every v ∈ V(G)-S, where N(v) is the neighborhood of v. The global offensive k-alliance number $\gamma {ₒ}^k\left(G\right)$ is the minimum cardinality of a global offensive k-alliance in G. We present different bounds on $\gamma {ₒ}^k\left(G\right)$ in terms of order, maximum degree, independence number, chromatic number and minimum degree.

Let G be a finite and simple graph with vertex set V (G), and let f V (G) → {−1, 1} be a two-valued function. If ∑x∈N|v| f(x) ≤ 1 for each v ∈ V (G), where N[v] is the closed neighborhood of v, then f is a signed 2-independence function on G. The weight of a signed 2-independence function f is w(f) =∑v∈V (G) f(v). The maximum of weights w(f), taken over all signed 2-independence functions f on G, is the signed 2-independence number α2s(G) of G. In this work, we mainly present upper bounds on α2s(G),...

Let $A$ be an $n\times n$ symmetric, irreducible, and nonnegative matrix whose eigenvalues are ${\lambda }_1>{\lambda }_2\ge ...\ge {\lambda }_n$. In this paper we derive several lower and upper bounds, in particular on ${\lambda }_2$ and ${\lambda }_n$, but also, indirectly, on $\mu ={max}_{2\le i\le n}\left|{\lambda }_i\right|$. The bounds are in terms of the diagonal entries of the group generalized inverse, $Q^{\#}$, of the singular and irreducible M-matrix $Q={\lambda }_{1}I-A$. Our starting point is a spectral resolution for $Q^{\#}$. We consider the case of equality in some of these inequalities and we apply our results to the algebraic connectivity of undirected...