Let \(M\) be a graph, and let \(H(M)\) denote the homeomorphism class of \(M\), that is, the set of all graphs obtained from \(M\) by replacing every edge by a `chain’ of edges in series. Given \(M\) it is possible, either using the `chain polynomial’ introduced by E. G. Whitehead and myself (Discrete Math. \(204(1999) 337-356)\) or by ad hoc methods, to obtain an expression which subsumes the chromatic polynomials of all the graphs in \(H(M)\). It is a function of the number of colors and the lengths of the chains replacing the edges of \(M\). This function contains complete information about the chromatic properties of these graphs. In particular, it holds the answer to the question “Which pairs of graphs in \(H(M)\) are chromatically equivalent”. However, extracting this information is not an easy task.

In this paper, I present a method for answering this question. Although at first sight it appears to be wildly impractical, it can be persuaded to yield results for some small graphs. Specific results are given, as well as some general theorems. Among the latter is the theorem that, for any given integer \(\gamma\), almost all cyclically \(3\)-connected graphs with cyclomatic number \(\gamma\) are chromatically unique.

The analogous problem for the Tutte polynomial is also discussed, and some results are given.

Let \(G\) be a simple graph of order \(p \geq 2\). A proper \(k\)-total coloring of a simple graph \(G\) is called a \(k\)-vertex distinguishing proper total coloring (\(k\)-VDTC) if for any two distinct vertices \(u\) and \(v\) of \(G\), the set of colors assigned to \(u\) and its incident edges differs from the set of colors assigned to \(v\) and its incident edges. The notation \(\chi_{vt}(G)\) indicates the smallest number of colors required for which \(G\) admits a \(k\)-VDTC with \(k \geq \chi_{vt}(G)\). For every integer \(m \geq 3\), we will present a graph \(G\) of maximum degree \(m\) such that \(\chi_{vt}(G) < \chi_{vt}(H)\) for some proper subgraph \(H \subseteq G\).

Let \(G = (V,E)\) be a graph. Let \(\gamma(G)\) and \(\gamma_t(G)\) be the domination and total domination number of a graph \(G\), respectively. The \(\gamma\)-criticality and \(\gamma_t\)-criticality of Harary graphs are studied. The Question \(2\) of the paper [W. Goddard et al., The Diameter of total domination vertex critical graphs, Discrete Math. \(286 (2004), 255-261]\) is fully answered with the family of Harary graphs. It is answered to the second part of Question \(1\) of that paper with some Harary graphs.

Let \(G\) be a connected graph. The hyper-Wiener index \(WW(G)\) is defined as \(WW(G) = \frac{1}{2}\sum_{u,v \in V(G)} d(u,v) + \frac{1}{2} \sum_{u,v \in V(G)} d^2(u,v),\) with the summation going over all pairs of vertices in \(G\) and \(d(u,v)\) denotes the distance between \(u\) and \(v\) in \(G\). In this paper, we determine the upper or lower bounds on hyper-Wiener index of trees with given number of pendent vertices, matching number, independence number, domination number, diameter, radius, and maximum degree.

A large set of resolvable Mendelsohn triple systems of order \(v\), denoted by \(\text{LRMTS}(v)\), is a collection of \(v-2\) \(\text{RMTS}(v)\)s based on \(v\)-set \(X\), such that every Mendelsohn triple of \(X\) occurs as a block in exactly one of the \(v-2\) \(\text{RMTS}(v)\)s. In this paper, we use \(\text{TRIQ}\) and \(\text{LR-design}\) to present a new product construction for \(\text{LRMTS}(v)\)s. This provides some new infinite families of \(\text{LRMTS}(v)\)s.

In this paper, we investigate the existence of nontrivial solutions for the equation \(y(G \Box H) – \gamma(G) \gamma(H)\) fixing one factor. For the complete bipartite graphs \(K_{m,n}\), we characterize all nontrivial solutions when \(m = 2, n \geq 3\) and prove the nonexistence of solutions when \(m \geq 2, n \leq 3\). In addition, it is proved that the above equation has no nontrivial solution if \(A\) is one of the graphs obtained from \(G\), the cycle of length \(n\), either by adding a vertex and one pendant edge joining this vertex to any vertex to any \(v\in V(C_n)\), or by adding one chord joining two alternating vertices of \(C_n\).

For a graph \(G = (V(G), E(G))\), let \(i(G)\) be the number of isolated vertices in \(G\). The isolated toughness of \(G\) is defined as
\(I(G) = \min\left\{\frac{|S|}{i(G-S)}: S \subseteq V(G), i(G-S) \geq 2\right\}\) if \(G\) is not complete; \(I(G) = |V(G)|-1\) otherwise. In this paper, several sufficient conditions in terms of isolated toughness are obtained for the existence of \([a, b]\)-factors avoiding given subgraphs, e.g., a set of vertices, a set of edges and a matching, respectively.

In a graph \(G\), the distance \(d(u,v)\) between a pair of vertices \(u\) and \(v\) is the length of a shortest path joining them. The eccentricity \(e(u)\) of a vertex \(u\) is the distance to a vertex farthest from \(u\). The minimum eccentricity is called the radius of the graph and the maximum eccentricity is called the diameter of the graph. The radial graph \(R(G)\) based on \(G\) has the vertex set as in \(G\). Two vertices \(u\) and \(v\) are adjacent in \(R(G)\) if the distance between them in \(G\) is equal to the radius of \(G\). If \(G\) is disconnected, then two vertices are adjacent in \(R(G)\) if they belong to different components. The main objective of this paper is to find a necessary and sufficient condition for a graph to be a radial graph.

Let \(\{T, T’\}\) be a Latin bitrade. Then \(T\) (and \(T’\)) is said to be \((r,c,e)\)-homogeneous if each row contains precisely \(r\) entries, each column contains precisely \(c\) entries, and each entry occurs precisely \(e\) times. An \((r,c,e)\)-homogeneous Latin bitrade can be embedded on the torus only for three parameter sets, namely \((r,c,e) = (3,3,3), (4,4,2)\), or \((6,3,2)\). The first case has been completely classified by a number of authors. We present classifications for the other two cases.

In this paper, we prove an interesting property of rook polynomials for \(2\)-D square boards and extend that for rook polynomials for \(3\)-D cubic, and \(r\)-D “hypercubic” boards. In particular, we prove that for \(r\)-D rook polynomials the modulus of the sum of their roots equals their degree. We end with some further questions, mainly for the \(2\)-D and \(3\)-D case, that could serve as future projects.