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.

A family \(\mathcal{F}\) of finite sets is said to have property \(B\) if there exists a set \(S\) such that \(0 < |{S} \cap F| < |F|\) for all \(F \in \mathcal{F}\). Denote by \(m_N(n)\) the least integer \(m\) for which there exists a family \(\mathcal{F}\) of \(m\) \(n\)-element subsets of a set \(V\) of size \(N\) such that \(\bigcup \mathcal{F} = V\) and which does not have property \(B\). We give constructions which yield upper bounds for \(m_N(4)\) for certain values of \(N\).

Let \(G\) be a connected graph and \(\mathcal{V}^*\) the set of all spanning trees except stars in \(G\). An edge in a spanning tree is called `inner’ if the edge is not incident to endvertices. Define an adjacency relation in \(\mathcal{V}^*\) as follows: two spanning trees \(t_1\) and \(t_2 \in \mathcal{V}^*\) are called to be adjacent if there exist inner edges \(e_i \in E(t_i)\) such that \(t_1 – e_1 = t_2 – e_2\). The resultant graph is a subgraph of the tree graph, and we call it simply a trunk graph. The purpose of this paper is to show that if a \(2\)-connected graph with at least five vertices is \(k\)-edge connected, then its trunk graph is \((k-1)\)-connected.

Let \(\tau(n)\) denote Ramanujan’s tau function. We obtain an identity that involves \(\tau(n)\) and \(\sigma(n)\), as well as some apparently new congruence properties of \(\tau(n)\) with respect to the moduli \(23\) and \(5\).

For loopless multigraphs \(G\), the total choice number is asymptotically equal to its fractional counterpart as the latter invariant tends to infinity. If \(G\) is embedded in the plane, then the edge-face and entire choice numbers exhibit the same “asymptotically good” behaviour. These results are based mainly on an analogous theorem of Kahn [5] for the list-chromatic index. Together with work of Kahn and others, our three results give a complete answer to a natural question: which of the seven invariants associated with list-colouring the nonempty subsets of \(\{V, E, F\}\) are asymptotically good?

In 1970, Behzad, Chartrand and Wall conjectured that the girth of every \(r\)-regular digraph \(G\) of order \(n\) is at most \(\left\lceil \frac{n}{r} \right\rceil\). The conjecture follows from a theorem of Menger and Dirac if \(G\) has strong connectivity \(x = r\). We show that any digraph with minimum in-degree and out-degree at least \(r\) has girth at most \(\left\lceil \frac{n}{r} \right\rceil\) if \(\kappa = r – 1\). We also find from the literature a family of counterexamples to a conjecture of Seymour.

In this paper, we give an alternative proof for the fact that the graph obtained by overlapping the cycle \(C_m\) (\(m \geq 3\)) and the complete bipartite graph \(K_{2,s}\) (\(s \geq 1\)) at an edge is uniquely determined by its chromatic polynomial. This result provides a partial solution to a question raised in [7].

Let \(G\) be a simple graph with \(n\) vertices. \(p(G,k)\) denotes the number of ways in which one can select \(k\) independent edges in \(G\) (\(k \geq 1\)). Let \(p(G,0) = 1\) for all \(G\).
The matching polynomial \(\alpha(G)\) of a graph \(G\) is given by:
\[\alpha(G) = \alpha(G,x) = \sum_{k=0}^{\left[\frac{n}{2}\right]} (-1)^k p(G,k) x^{n-2k}\]

In this article, we give the matching polynomials of the complete \(n\)-partite graph with a differential operator.

The List Edge Coloring Conjecture states that for every graph, the chromatic index equals the choice index. We prove the conjecture for outerplanar graphs with maximum degree at least five.

Cycle prefix digraphs are a class of Cayley coset graphs with many remarkable properties, such as:Symmetry Large number of nodes for a given degree and diameter Simple shortest path routing Hamiltonicity Optimal connectivity Others.
In this paper, we show that the cycle prefix digraphs, like the Kautz digraphs, contain cycles of all lengths \(l\), with \(l\) between two and \(N\), the order of the digraph, except for \(N-1\).

Let \(G\) be a cubic bipartite plane graph that has a perfect matching. If \(M\) is any perfect matching of \(G\), then \(G\) has a face that is \(M\)-alternating.If \(f\) is any face of \(G\), then there is a perfect matching \(M\) such that \(f\) is \(M\)-alternating.There is a simple algorithm for visiting all perfect matchings of \(G\) beginning at one.
There are infinitely many cubic plane graphs that have perfect matchings but whose matching transformation graphs are completely disconnected.
Several problems are proposed.

In this paper, we calculate the jump number of the product of an ordered set and a chain.

In [1], [2] we can find results concerning kernel-perfect graphs and solvable graphs. These concepts are related to kernels of a digraph. The authors of [2] consider two graph constructions: the join of two graphs and duplication of a vertex. These kinds of graphs preserve kernel-perfectness and solvability of their orientations. In this paper we generalize results from [2] applying them to \((k,l)\)-kernels and two operations: generalized join and duplication of a subset of vertices. The concept of a \((k,l)\)-kernel of a digraph was introduced in [8] and was studied in [6], [7], and [9]. In our considerations we take advantage of the asymmetrical part of digraphs, which was used by H. Galeana-Sanchez in [6] in the proof of a sufficient condition for a digraph to have a \((k, l)\)-kernel.

With the help of computer algorithms, we improve the lower bound on the Ramsey multiplicity of \(K_4\) and thus show that the exact value of it is equal to \(9\).

For two integers \(k > 0\) and \(s (\geq 0\)), a cycle of length \(s\) is called an \((s \mod k)\)-cycle if \(l \equiv s \mod k\). In this paper, the following conjecture of Chen, Dean, and Shreve [5] is proved:Every \(2\)-connected graph with at least six vertices and minimum degree at least three contains a (\(2 \mod 4\))-cycle.

In this paper we present graceful and nearly graceful labelings of some graphs. In particular, we show, graceful labelings of the \(kC_4-snake\) (for the general case),\(kC_6\) and \(kC_{12}-snakes\) (for the even case),and also establish some conditions to obtain graceful labelings of \(kC_{4n}-snakes\) with some related results. Moreover, for the linear \(kC_6\)-snake, we show:a graceful labeling when \(k\) is even,a nearly graceful labeling when \(k\) is odd.We also explore the connection of these labelings with more restrictive variations of graceful ones.

By considering the order of the largest induced bipartite subgraph of \(G\), Hagauer and Klaviar [4] were able to improve the bounds first published by V. G. Vizing [6] for the independence number of the Cartesian product \(G \Box H\) for any graph \(H\). In this paper, we study maximum independent sets in \(G \Box H\) when \(G\) is a caterpillar, and derive bounds for the independence number when \(H\) is bipartite. The upper bound we produce is less than or equal to that in [4] when \(H\) is also a caterpillar, and is shown to be strictly smaller when \(H\) comes from a restricted class of caterpillars.

Let \(T\) be a spanning tree of a graph \(G\). This paper is concerned with the following operation: we remove an edge \(e \in E(T)\) from \(T\), and then add an edge \(f \in E(G) – E(T)\) so that \(T – e + f\) is a spanning tree of \(G\). We refer to this operation of obtaining \(T – e + f\) from \(T\) as the transfer of \(e\) to \(f\). We prove that if \(G\) is a \(2\)-connected graph with \(|V(G)| \geq 5\), and if \(T_1\) and \(T_2\) are spanning trees of \(G\) which are not stars, then \(T_1\) can be transformed into \(T_2\) by repeated applications of a transfer of a nonpendant edge (an edge \(xy\) of a tree \(T\) is called a nonpendant edge of \(T\) if both of \(x\) and \(y\) have degree at least \(2\) in \(T\)).

We provide upper estimates on the weak exponent of indecomposability of an irreducible Boolean matrix.

The toughness \(t(G)\) of a noncomplete graph \(G\) is defined as

\[t(G) = \min\left\{\frac{|S|}{\omega(G-S)} \mid S \subseteq V(G), \omega(G-S) \geq 2\right\},\]

where \(\omega(G-S)\) is the number of components of \(G-S\). We also define \(t(K_n) = +\infty\) for every \(n\).

The middle graph \(M(G)\) of a graph \(G\) is the graph obtained from \(G\) by inserting a new vertex into every edge of \(G\) and by joining by edges those pairs of these new vertices which lie on adjacent edges of \(G\).

In this article, we give the toughness of the middle graph of a graph, and using this result we also give a sufficient condition for the middle graph to have a \(k\)-factor.

This paper gives constructions of balanced incomplete block designs and group divisible designs with \(k = 7, 8,\) or \(9\), and \(\lambda = 1\). The first objective is to give constructions for all possible cases with the exception of \(40, 78,\) and \(157\) values of \(v\). Many of these initial exceptions have now been removed by Abel. In an update section, more are removed; group divisible designs with groups of size \(k(k-1)\) are constructed for \(k = 7\) and \(8\) with \(124\) and \(87\) exceptions; it is also established that \(v \geq 294469\) and \(v \equiv 7\) mod \(42\) suffices for the existence of a resolvable balanced incomplete block design with \(k = 7\). Group divisible designs with group size \(k\) and resolvable designs are constructed.