In this paper, we show that a graph \(G\) with \(e \geq 6\) edges contains at most \(\frac{h(h-1)(h-2)(h-3)}{2}\) paths of length three, where \(h \geq 0\) satisfies \(\frac{h(h-1)}{2} = e\). It follows immediately that \(G\) contains at most \(\frac{h(h-1)(h-2)(h-3)}{8}\) cycles of length four. For \(e > 6\), the bounds will be attained if and only if \(h\) is an integer and \(G\) is the union of \(K_h\) and isolated vertices. The bounds improve those found recently by Bollobás and Sarkar.

Let \(p > 2\) be a prime, and \(G = C_{p^{e_1}} \oplus \ldots \oplus C_{p^{e_k}}\) (\(1 \leq e_1 \leq \cdots \leq e_k\)) a finite abelian \(p\)-group. We prove that \(1 + 2\sum_{i=1}^{k}(p^{e_i} – 1)\) is the smallest integer \(t\) such that every sequence of \(t\) elements in \(G\) contains a zero-sum subsequence of odd length. As a consequence, we derive that if \(p^{e_k} \geq 1 + \sum_{i=1}^{k-1} (p^{e_i} – 1)\), then every sequence of \(4p^{e_k} – 3 + 2\sum_{i=1}{k-1} (p^{e_i} – 1)\) elements in \(G\) contains a zero-sum subsequence of length \(p^{e_k}\).

Solutions for the edge-isoperimetric problem on the graphs of the triangular and hexagonal tessellations of the Euclidean plane are given. The proofs are based on the fact that their symmetry group is Coxeter. In each case, there is a certain nice quotient of the stability order of the graph (which is itself a quotient of the Bruhat order of the Coxeter group by a parabolic subgroup).

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.