Counting the number of maximal independent sets is \(\#P\)-complete even for chordal graphs. We prove that the number of maximal independent sets in a subclass \({G}_n^R\) (Right power set graphs) of chordal graphs can be computed in polynomial time using Golomb’s nonlinear recurrence relation. We provide a recursive construction of \({G}_n^R\) and prove that there are \(2^\frac{|V({G}_n^R)|+1}{4}\) maximum independent sets in \({G}_n^R\). We also provide a polynomial-time algorithm to solve the maximum independent set problem (MISP) in a superclass \(\mathcal{F}_n\) of the complement of \({G}_n^R\).

The eccentric connectivity index of the molecular graph \(G\) was proposed by Sharma, Goswami, and Madan in 1997 \cite{17}. This index is defined as \(\xi^c(G) = \sum_{v\in V(G)} \deg(v) \, ec(v)\), where \(\deg(v)\) is the degree of vertex \(v\) in \(G\) and eccentricity \(ec(v)\) is the largest distance between \(v\) and any other vertex of \(G\). Thus, in this paper, we established the general formulas for the eccentric connectivity index of joining a special graph to its paths and of joining two different graphs by a path. Proofs were also provided.

We present a design for a seven-game tournament of the \(7\)-player board game \({Diplomacy}\), in which each player plays each country one time and each pair of players shares a border either \(4\) or \(5\) times. It is impossible for each pair of players to share a border the same number of times in such a tournament, and so the tournament presented is the most “balanced” possible in this sense. A similarly balanced tournament can be constructed for a generalized version of the game involving an arbitrary number of countries. We also present an infinite family of graphs that cannot be balanced.

A graph \(G = (V, E)\) with \(p\) vertices and \(q\) edges is called a Harmonic mean graph if it is possible to label the vertices \(v \in V\) with distinct labels \(f(v)\) from \(1, 2, \dots, q+1\) in such a way that when each edge \(e = uv\) is labeled with \(f(e = uv) = \left\lceil\frac{2f(u)f(v)}{f(u) + f(v)}\right\rceil\) or \(\left\lfloor \frac{2f(u)f(v)}{f(u) + f(v)} \right\rfloor\), then the edge labels are distinct. In this case, \(f\) is called a Harmonic mean labeling of \(G\). In this paper, we investigate some new families of Harmonic mean graphs.

The clique sum \(\Sigma = G[G_1,G_2,\ldots,G_n]\) is the lexicographic sum over \(G\) where each fiber \(G_i\) is a clique. We show the reconstruction number of \(\Sigma\) is three unless \(\Sigma\) is vertex transitive and \(G\) has order at least two. In the latter case, it follows that \(\Sigma = G[K_m]\) is a lexicographic product, and the reconstruction number is \(m+2\). This complements the bounds of Brewster, Hahn, Lamont, and Lipka. It also extends the work of Myrvold and Molina.

We provide a new proof of a result of Hanson and Toft classifying the maximum-size \(K_r\)-free graphs on \(n\) vertices with chromatic number at least \(r\).

Much research has been done on the edge decomposition of \(\lambda\) copies of the complete graph \(G\) with respect to some specified subgraph \(H\) of \(G\). This is equivalent to the investigation of \((G, H)\)-designs of index \(\lambda\). In this paper, we present a fundamental theorem on the decomposition of \(\lambda\) copies of a complete bipartite graph. As an application of this result, we show that necessary conditions are sufficient for the decomposition of \(\lambda\) copies of a complete bipartite graph into several multi-subgraphs \(H\) with a number of vertices less than or equal to \(4\) and the number of edges less than or equal to \(4\), with some exceptions where decompositions do not exist. These decomposition problems are interesting to study as various decompositions do not exist even when necessary conditions are satisfied.

If the integer \(r \geq 2\), say that a composition of the natural number \(n\) is \(r\)-\({regular}\) if no part is divisible by \(r\). Let \(c_r(n)\) denote the number of \(r\)-regular compositions of \(n\) (with \(c_r(0) = 1\)). We show that \(c_r(n)\) satisfies a linear recurrence of order \(r\). We also obtain asymptotic estimates for \(c_r(n)\), and we evaluate \(c_r(n)\) for \(2 \leq r \leq 5\) and \(1 \leq n \leq 10\).

Using only the skein relation and some combinatorics, we find a closed form for the Conway polynomial of \((m,3)\) torus links and a trio of recurrence relations that define the Conway polynomial of any \((m,4)\) torus link.

For positive integers \(c\) and \(d\), let \(K_{c\times d}\) denote the complete multipartite graph with \(c\) parts, each containing \(d\) vertices. Let \(G\) with \(n\) edges be the union of two vertex-disjoint even cycles. We use graph labelings to show that there exists a cyclic \(G\)-decomposition of \(K_{(2n+1)\times t}\), \(K_{(n/2+1)\times 4t}\), \(K_{5\times (n/2)t}\), and of \(K_{2\times 2nt}\) for every positive integer \(t\). If \(n \equiv 0 \pmod{4}\), then there also exists a cyclic \(G\)-decomposition of \(K_{(n+1)\times 2t}\), \(K_{(n/4+1)\times 8t}\), \(K_{9\times (n/4)t}\), and of \(K_{3\times nt}\) for every positive integer \(t\).