For a graph \(G = (V,E)\), a set \(S \subseteq V\) is \(total\; irredundant\) if for every vertex \(v \in V\), the set \(N[v]- N[S – \{v\}]\) is not empty. The \(total \;irredundance\; number\) \(ir_t(G)\) is the minimum cardinality of a maximal total irredundant set of \(G\). We study the structure of the class of graphs which do not have any total irredundant sets; these are called \(ir_t(0)\)-graphs. Particular attention is given to the subclass of \(ir_t(0)\)-graphs whose total irredundance number either does not change (stable) or always changes (unstable) under arbitrary single edge additions. Also studied are \(ir_t(0)\)-graphs which are either stable or unstable under arbitrary single edge deletions.

Let \(n_1, n_2, \ldots, n_k\) be integers of at least two. Johansson gave a minimum degree condition for a graph of order exactly \(n_1 + n_2 + \cdots + n_k\) to contain \(k\) vertex-disjoint paths of order \(n_1, n_2, \ldots, n_k\), respectively. In this paper, we extend Johansson’s result to a corresponding packing problem as follows. Let $G$ be a connected graph of order at least \(n_1 + n_2 + \cdots + n_k\). Under this notation, we show that if the minimum degree sum of three independent vertices in \(G\) is at least:

\[3(\lfloor \frac{n_1}{2}\rfloor+\lfloor \frac{n_2}{2}\rfloor+ \ldots +\lfloor \frac{n_k}{2}\rfloor)\]

then \(G\) contains \(k\) vertex-disjoint paths of order \(n_1, n_2, \ldots, n_k\), respectively, or else \(n_1 = n_2 = \cdots = n_e = 3\), or \(k = 2\) and \(n_1 = n_2 = \text{odd}\). The graphs in the exceptional cases are completely characterized. In particular, these graphs have more than \(n_1 + n_2 + \cdots + n_k\) vertices.

In this work, first, we present sufficient conditions for a bipartite digraph to attain optimum values of a stronger measure of connectivity, the so-called superconnectivity. To be more precise, we study the problem of disconnecting a maximally connected bipartite (di)graph by removing nontrivial subsets of vertices or edges. Within this framework, both an upper-bound on the diameter and Chartrand type conditions to guarantee optimum superconnectivities are obtained. Secondly, we show that if the order or size of a bipartite (di)graph is small enough then its vertex connectivity or edge-connectivity attain their maximum values. For example, a bipartite digraph is maximally edge-connected if \(\delta^+(x)+\delta^+(y)\geq \lceil\frac{n+1}{2}\rceil\) for all pair of vertices \(x, y\) such that \(d(x,y) \geq 4\). This result improves some conditions given by Dankelmann and Volkmann in [12] for the undirected case.

The convex polyhedron of all real-valued monotone functions defined on a finite poset is an unbounded variant of the order polytope described by Stanley. If the undirected covering graph of the poset is acyclic, then the lattice of non-empty faces of this polyhedron is a Boolean lattice. In every other case, both semimodularity and dual semimodularity fail.

In a paper of Cockayne et al., the authors establish an upper and a lower bound for the dominating number of the complete grid graph \(G_{n,n}\), of order \(n^2\). Namely, they proved a “formula”, and cited two questions of Paul Erdős. One of these questions was “Can we improve the order of the difference between lower and upper bounds from \(\frac{n}{5}\) to \(\frac{n}{2}\)?”. Our aim here is to give a positive answer to this question.

Let \(D = (V_1, V_2; A)\) be a directed bipartite graph with \(|V_1| = |V_2| = n \geq 2\). Suppose that \(d_D(x) + d_D(y) \geq 3n\) for all \(x \in V_1\) and \(y \in V_2\). Then, with one exception, \(D\) contains two vertex-disjoint directed cycles of lengths \(2s\) and \(2t\), respectively, for any two positive integers \(s\) and \(t\) with \(s+t \leq n\).

The edge clique graph of a graph \(G\) is one having as vertices the edges of \(G\), two vertices being adjacent if the corresponding edges of \(G\) belong to a common clique.

Recently, Hsu and Shiue [10] obtained a kind of generalized Stirling number pairs with three free parameters and proved some of its properties. Here, some properties analogous to those of ordinary Stirling numbers are investigated, viz. horizontal recurrence relations, vertical recurrence relations, rational generating function, and explicit formulas. Furthermore, a kind of infinite sum which is useful in some combinatorial applications of the generalized Stirling numbers, is evaluated.

Clique graphs of several classes of graphs have been already characterized. Trees, interval graphs, chordal graphs, block graphs, clique-Helly graphs are some of them. However, no characterization of clique graphs of circular-arc graphs and some of their subclasses is known. In this paper, we present a characterization theorem of clique graphs of Helly circular-arc graphs and prove that this subclass of circular-arc graphs is properly contained in the intersection between proper circular-arc graphs, clique-Helly circular-arc graphs and Helly circular-arc graphs. Furthermore, we prove properties about the \(2^{\text{nd}}\) iterated clique graph of this family of graphs.

Let \(g: \mathbb{F}^m \to \mathbb{F}\) be a linear function on the vector space \(\mathbb{F}^m\) over a finite field \(\mathbb{F}\). A subset \(S \subsetneqq \mathbb{F}\) is called \(g\)-thin iff \(g(S^m) \subsetneqq \mathbb{F}\). In case \(\mathbb{F}\) is the field \(\mathbb{Z}_p\) of odd prime order, if \(S\) is \(g\)-thin and if \(m\) divides \(p-1\), then it is shown that \(|S| \leq \frac{p-1}{m}\). We also show that in certain cases \(S\) must be an arithmetic progression, and the form of the linear function \(g\) can be characterized.