The Hoffman ratio bound, Lovász theta function, and Schrijver theta function are classical upper bounds for the independence number of graphs, which are useful in graph theory, extremal combinatorics, and information theory. By using generalized inverses and eigenvalues of graph matrices, we give bounds for independence sets and the independence number of graphs. Our bounds unify the Lovász theta function, Schrijver theta function, and Hoffman-type bounds, and we obtain the necessary and sufficient conditions of graphs attaining these bounds. Our work leads to some simple structural and spectral conditions for determining a maximum independent set, the independence number, the Shannon capacity, and the Lovász theta function of a graph.

We study several parameters of a random Bienaymé–Galton–Watson tree $T_n$ of size $n$ defined in terms of an offspring distribution $\xi$ with mean $1$ and nonzero finite variance $\sigma ^2$ . Let $f(s)=\mathbb{E}\{s^\xi \}$ be the generating function of the random variable $\xi$ . We show that the independence number is in probability asymptotic to $qn$ , where $q$ is the unique solution to $q = f(1-q)$ . One of the many algorithms for finding the largest independent set of nodes uses a notion of repeated peeling away of all leaves and their parents. The number of rounds of peeling is shown to be in probability asymptotic to $\log n/\log (1/f'(1-q))$ . Finally, we study a related parameter which we call the leaf-height. Also sometimes called the protection number, this is the maximal shortest path length between any node and a leaf in its subtree. If $p_1 = \mathbb{P}\{\xi =1\}\gt 0$ , then we show that the maximum leaf-height over all nodes in $T_n$ is in probability asymptotic to $\log n/\log (1/p_1)$ . If $p_1 = 0$ and $\kappa$ is the first integer $i\gt 1$ with $\mathbb{P}\{\xi =i\}\gt 0$ , then the leaf-height is in probability asymptotic to $\log _\kappa \log n$ .

The paper introduces a graph theory variation of the general position problem: given a graph $G$, determine a largest set $S$ of vertices of $G$ such that no three vertices of $S$ lie on a common geodesic. Such a set is a max-gp-set of $G$ and its size is the gp-number $\text{gp}(G)$ of $G$. Upper bounds on $\text{gp}(G)$ in terms of different isometric covers are given and used to determine the gp-number of several classes of graphs. Connections between general position sets and packings are investigated and used to give lower bounds on the gp-number. It is also proved that the general position problem is NP-complete.

The annihilating-ideal graph of a commutative ring $R$, denoted by $\mathbb{A}\mathbb{G}\left( R \right)$, is a graph whose vertex set consists of all non-zero annihilating ideals and two distinct vertices $I$ and $J$ are adjacent if and only if $IJ\,=\,\left( 0 \right)$. Here we show that if $R$ is a reduced ring and the independence number of $\mathbb{A}\mathbb{G}\left( R \right)$ is finite, then the edge chromatic number of $\mathbb{A}\mathbb{G}\left( R \right)$ equals its maximum degree and this number equals ${{2}^{\left| \min \left( R \right) \right|-1}}-\,1$; also, it is proved that the independence number of $\mathbb{A}\mathbb{G}\left( R \right)$ equals ${{2}^{\left| \min \left( R \right) \right|-1}}$, where $\min \left( R \right)$ denotes the set of minimal prime ideals of $R$. Then we give some criteria for a graph to be isomorphic with an annihilating-ideal graph of a ring. For example, it is shown that every bipartite annihilating-ideal graph is a complete bipartite graph with at most two horns. Among other results, it is shown that a finite graph $\mathbb{A}\mathbb{G}\left( R \right)$ is not Eulerian, and that it is Hamiltonian if and only if $R$ contains no Gorenstain ring as its direct summand.

The classical first and second Zagreb indices of a graph $G$ are defined as $M_{1}(G)=\sum _{v\in V(G)}d(v)^{2}$ and $M_{2}(G)=\sum _{e=uv\in E(G)}d(u)d(v),$ where $d(v)$ is the degree of the vertex $v$ of $G.$ Recently, Furtula et al. [‘On difference of Zagreb indices’, Discrete Appl. Math.178 (2014), 83–88] studied the difference of $M_{1}$ and $M_{2},$ and showed that this difference is closely related to the vertex-degree-based invariant $RM_{2}(G)=\sum _{e=uv\in E(G)}[d(u)-1][d(v)-1]$, the reduced second Zagreb index. In this paper, we present sharp bounds for the reduced second Zagreb index, given the matching number, independence number and vertex connectivity, and we also completely determine the extremal graphs.