The Merrifield-Simmons index of a graph is defined as the total number of its independent sets, including the empty set. Recently, Heuberger and Wagner [Maximizing the number of independent subsets over trees with bounded degree, J. Graph Theory, \(58 (2008) 49-68\)] investigated the problem of determining the trees with the maximum Merrifield-Simmons index among trees of restricted maximum degree. In this note, we consider the problem of determining the graphs with the maximum Merrifield-Simmons index among connected graphs of restricted minimum degree. Let \(\mathcal{G}_\delta(n)\) denote the set of connected graphs of \(n\) vertices and minimum degree \(\delta\). We first conjecture that among all graphs in \(\mathcal{G}_\delta(n)\), \(n \geq 2\delta\), the graphs with the maximum Merrifield-Simmons index are isomorphic to \(K_{\delta,n-\delta}\) or \(C_5\). Then we affirm this conjecture for the case of \(\delta = 1, 2, 3\).

Cahit and Yilmaz \([15]\) called a graph \(G\) is \(E_k\)-cordial if it is possible to label its edges with numbers from the set \(\{0, 1, \ldots, k-1\}\) in such a way that, at each vertex \(V\) of \(G\), the sum modulo \(k\) of the labels on the edges incident with \(V\) satisfies the inequalities \(|m_(i) – m_(j)| \leq 1\) and \(|n_(i) – n_(j)| \leq 1\), where \(m_(s)\) and \(n_(t)\) are, respectively, the number of edges labeled with \(s\) and the number of vertices labeled with \(t\). In this paper, we give a necessary condition for a graph to be \(E_k\)-cordial for certain \(k\). We also give some new families of \(E_{k}\)-cordial graphs and we prove Lee’s conjecture about the edge-gracefulness of the disjoint union of two cycles.

The Harmonic index \(H(G)\) of a graph \(G\) is defined as the sum of weights \(\frac{2}{d(u)+d(v)}\) of all edges \(uv\) of \(G\), where \(d(u)\) denotes the degree of a vertex \(u\) in \(G\). In this paper, we consider the Harmonic index of unicyclic graphs with a given order. We give the lower and upper bounds for Harmonic index of unicyclic graphs and characterize the corresponding extremal graphs.

We discuss here some necessary and sufficient conditions for a graph to be prime. We give a procedure to determine whether or not a graph is prime.

The higher order connectivity index is a graph invariant defined as \(^{h}{}{\chi}(G) = \sum_{u_1u_2\ldots u_{h+1}} \frac{1}{\sqrt{{d_{u_1}d_{u_2}\ldots d_{u_{h+1}}}}}\), where the summation is taken over all possible paths of length \(h\) and \(d_{u_i}\) denotes the degree of the vertex \(u_i\) of graph \(G\). In this paper, an exact expression for the fourth order connectivity index of Phenylenes is given.

This paper deals with two types of graph labelings, namely, the super \((a, d)\)-edge antimagic total labeling and super \((a, d)\)-vertex antimagic total labeling on the Harary graph \(C_n^t\). We also construct the super edge-antimagic and super vertex-antimagic total labelings for a disjoint union of \(k\) identical copies of the Harary graph.

The sum-Balaban index of a connected graph \(G\) is defined as

\[J_e(G) = \frac{m}{\mu+1}\sum_{uv \in E(G)} {(D_u + D_v)}^{-\frac{1}{2}},\]

where \(D_u\) is the sum of distances between vertex \(u\) and all other vertices, \(\mu\) is the cyclomatic number, \(E(G)\) is the edge set, and \(m = |E(G)|\). We establish various upper and lower bounds for the sum-Balaban index, and determine the trees with the largest, second-largest, and third-largest as well as the smallest, second-smallest, and third-smallest sum-Balaban indices among the \(n\)-vertex trees for \(n \geq 6\).

A \((v,m,m-1)\)-BIBD \(D\) is said to be near resolvable (NR-BIBD) if the blocks of \(D\) can be partitioned into classes \(R_1, R_2, \ldots, R_v\) such that for each point \(x\) of \(D\), there is precisely one class having no block containing \(x\) and each class contains precisely \(v – 1\) points of the design. If a \((v,m,m-1)\)-NRBIBD has a pair of orthogonal near resolutions, it is said to be doubly resolvable and is denoted DNR\((v,m,m-1)\)-BIBD. A lot of work had been done for the existence of \((v,m,m-1)\)-NRBIBDs, while not so much is known for the existence of DNR\((v,m,m-1)\)-BIBDs except for the existence of DNR\((v,3,2)\)-BIBDs. In this paper, doubly disjoint \((mt+1,m,m-1)\) difference families \(((mt+1,m,m-1)\)-DDDF in short) which were called starters and adders in the previous paper by Vanstone, are used to construct DNR\((v,m,m-1)\)-BIBDs. By using Weil’s theorem on character sum estimates, an explicit lower bound for the existence of a \((mt+1,m,m-1)\)-DDDF and a DNR\((mt+1,m,m-1)\)-BIBD is obtained, where \(mt+1\) is a prime power, \((m,t)=1\). By using this result, it is also proved that there exist a \((v,4,3)\)-DDDF and a DNR\((v,4,3)\)-BIBD for any prime power \(v\equiv 5\pmod{8}\) and \(v\geq 5d\).

For a graph \(G\), Chartrand et al. defined the rainbow connection number \(rc(G)\) and the strong rainbow connection number \(src(G)\) in “G. Chartrand, G.L. John, K.A. McKeon, P. Zhang, Rainbow connection in graphs, Mathematica Bohemica, \(133(1)(2008) 85-98\)”. They raised the following conjecture: for two given positive integers \(a\) and \(b\), there exists a connected graph \(G\) such that \(rc(G) = a\) and \(src(G) = b\) if and only if \(a = b \in \{1,2\}\) or \(3 \leq a \leq b”\). In this short note, we will show that the conjecture is true.

The graph \(P_{a,b}\) is defined as the one obtained by taking \(b\) vertex-disjoint copies of the path \(P_{a+1}\) of length \(a\), coalescing their first vertices into one single vertex labeled \(u\) and then coalescing their last vertices into another single vertex labeled \(v\). K.M. Kathiresan showed that \(P_{2r,2m-1}\) is graceful and conjectured that \(P_{a,b}\) is graceful except when \((a,b) = (2r+1, 4s+2)\). In this paper, an algorithm for finding another graceful labeling of \(P_{2r,2}\) is provided, and \(P_{2r,2(2k+1)}\) is proved to be graceful for all positive \(r\) and \(k\).