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.

We enumerate all order ideals of a garland, a partially ordered set which generalizes crowns and fences. Moreover, we give some bijection between the set of such ideals and the set of certain kinds of lattice paths.

In this paper, we consider transformations between posets \(P\) and \(Q\), whose semi bound graphs are the same. Those posets with the same double canonical posets can be transformed into each other by a finite sequence of two kinds of transformations, called \(d\)-additions and \(d\)-deletions.