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\).

The chromatic sum of \(G\), denoted by \(\sum(G)\), is the minimum sum of vertex colors, taken over all proper colorings of \(G\) using natural numbers. In general, finding \(\sum(G)\) is NP-complete. This paper presents polynomial-time algorithms for finding the chromatic sum for unicyclic graphs and for outerplanar graphs.