A graph \(G\) is called integral or Laplacian integral if all the eigenvalues of the adjacency matrix \(A(G)\) or the Laplacian matrix \(Lap(G) = D(G) – A(G)\) of \(G\) are integers, where \(D(G)\) denotes the diagonal matrix of the vertex degrees of \(G\). Let \(K_{n,n+1} \equiv K_{n+1,n}\) and \(K_{1,p}[(p-1)K_p]\) denote the \((n+1)\)-regular graph with \(4n+2\) vertices and the \(p\)-regular graph with \(p^2 + 1\) vertices, respectively. In this paper, we shall give the spectra and characteristic polynomials of \(K_{n,n+1} \equiv K_{n+1,n}\) and \(K_{1,p}[(p-1)K_p]\) from the theory on matrices. We derive the characteristic polynomials for their complement graphs, their line graphs, the complement graphs of their line graphs, and the line graphs of their complement graphs. We also obtain the numbers of spanning trees for such graphs. When \(p = n^2 + n + 1\), these graphs are not only integral but also Laplacian integral. The discovery of these integral graphs is a new contribution to the search of integral graphs.

Balakrishnan et al. \([1, 2]\) have shown that every graph is a subgraph of a graceful graph and an elegant graph. Also Liu and Zhang \([4]\) have shown that every graph is a subgraph of a harmonious graph. In this paper we prove a generalization of these two results that any given set of graphs \(G_1,G_1,\ldots,G_i\) can be packed into a graceful/harmonious/elegant graph.

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.