We consider compositions or ordered partitions of the natural number n for which the largest (resp. smallest) summand occurs in the first position of the composition.

Let \(m \geq 4\) be a positive integer and let \({Z}_m\) denote the cyclic group of residues modulo \(m\). For a system \(L\) of inequalities in \(m\) variables, let \(R(L;2)\) (\(R(L;{Z}_m)\)) denote the minimum integer \(N\) such that every function \(\Delta: \{1,2,\ldots,N\} \to \{0,1\}\) (\(A: \{1,2,\ldots,N\} \to {Z}_m\)) admits a solution of \(L\), say \((z_1,\ldots,z_m)\), such that \(\Delta(x_1) = \Delta(x_2) = \cdots = \Delta(x_m)\) (such that \(\sum_{i=1}^{m}\Delta(x_i) = 0\)). Define the system \(L_1(m)\) to consist of the inequality \(x_2 – x_1 \leq x_m – x_3\), and the system \(L_2(m)\) to consist of the inequality \(x_{m – 2}-x_{1} \leq x_m – x_{m-1}\); where \(x_1 < x_2 < \cdots < x_m\) in both \(L_1(m)\) and \(L_2(m)\). The main result of this paper is that \(R(L_1(m);2) = R(L_1(m);{Z}_m) = 2m\), and \(R(L_2(m);2) = 6m – 15\). Furthermore, we support the conjecture that \(R(L_1(m);2) = R(L_1(m);{Z}_m)\) by proving it for \(m = 5\).

In a given graph \(G\), a set \(S\) of vertices with an assignment of colors is a defining set of the vertex coloring of \(G\), if there exists a unique extension of the colors of \(S\) to a \(\chi(G)\)-coloring of the vertices of \(G\). A defining set with minimum cardinality is called a smallest defining set (of vertex coloring) and its cardinality, the defining number, is denoted by \(d(G, \chi)\). We study the defining number of regular graphs. Let \(d(n,r, \chi = k)\) be the smallest defining number of all \(r\)-regular \(k\)-chromatic graphs with \(n\) vertices, and \(f(n,k) = \frac{k-2}{2(k-1)} +\frac{2+(k-2)(k-3)}{2(k-1)}\). Mahmoodian and Mendelsohn (1999) determined the value of \(d(n,k, \chi = k)\) for all \(k \leq 5\), except for the case of \((n,k) = (10,5)\). They showed that \(d(n,k, \chi = k) = \lceil f(n,k) \rceil\), for \(k \leq 5\). They raised the following question: Is it true that for every \(k\), there exists \(n_0(k)\) such that for all \(n \geq n_0(k)\), we have \(d(n,k, \chi = k) = \lceil f(n,k) \rceil\)?

Here we determine the value of \(d(n,k, \chi = k)\) for each \(k\) in some congruence classes of \(n\). We show that the answer for the question above, in general, is negative. Also, for \(k = 6\) and \(k = 7\) the value of \(d(n,k, \chi = k)\) is determined except for one single case, and it is shown that \(d(10,5, \chi = 5) = 6\).

Let \((T_i)_{i\geq 0}\) be a sequence of trees such that \(T_{i+1}\) arises by deleting the \(b_i\) vertices of degree \(\leq 1\) from \(T_i\). We determine those trees of given degree sequence or maximum degree for which the sequence \(b_0, b_1, \ldots\) is maximum or minimum with respect to the dominance order. As a consequence, we also determine trees of given degree sequence or maximum degree that are of maximum or minimum Balaban index.

In this paper, we give a complete characterization of the pseudogracefulness of cycles.

The maximal clique that contains an edge which is not contained in any other maximal cliques is called essential. A graph in which each maximal clique is essential is said to be maximal clique irreducible. Maximal clique irreducible graphs were introduced and studied by W.D. Wallis and G.-H. Zhang in \(1990\) \([6]\). We extend the concept and define a graph to be weakly maximal clique irreducible if the set of all essential maximal cliques is a set of least number of maximal cliques that contains every edge. We characterized the graphs for which each induced subgraph is weakly maximal clique irreducible in \([4]\). In this article, we characterize the line graphs which are weakly maximal clique irreducible and also the line graphs which are maximal clique irreducible.

A weighted graph is one in which every edge \(e\) is assigned a non-negative number, called the weight of \(e\). For a vertex \(v\) of a weighted graph, \(d^w(v)\) is the sum of the weights of the edges incident with \(v\). For a subgraph \(H\) of a weighted graph \(G\), the weight of \(H\) is the sum of the weights of the edges belonging to \(H\). In this paper, we give a new sufficient condition for a weighted graph to have a heavy cycle. Let \(G\) be a \(k\)-connected weighted graph where \(2 \leq k\). Then \(G\) contains either a Hamilton cycle or a cycle of weight at least \(2m/(k+1)\), if \(G\) satisfies the following conditions:(1)The weighted degree sum of any \(k\) independent vertices is at least \(m\),(2) \(w(xz) = w(yz)\) for every vertex \(z \in N(x) \cap N(y)\) with \(d(z,y) = 2\), and (3)In every triangle \(T\) of \(G\), either all edges of \(T\) have different weights or all edges of \(T\) have the same weight.

A circulant digraph \(G(a_1, a_2, \ldots, a_k)\), where \(0 < a_1 < a_2 < \ldots < a_k < |V(G)| = n\), is the vertex transitive directed graph that has vertices \(i+a_1, i+a_2, \ldots, i+a_k \pmod{n}\) adjacent to each vertex \(i\). We give the necessary and sufficient conditions for \(G(a_1, a_2)\) to be hamiltonian, and we prove that \(G(a, n-a, b)\) is hamiltonian. In addition, we identify the explicit hamiltonian circuits for a few special cases of sparse circulant digraphs.

We find a family of graphs each of which is not Hall \(t\)-chromatic for all \(t \geq 3\), and use this to prove that the same holds for the Kneser graphs \(K_{a,b}\) when \(a/b \geq 3\) and \(b\) is sufficiently large (depending on \(3 – (a/b)\)). We also make some progress on the problem of characterizing the graphs that are Hall \(t\)-chromatic for all \(t\).