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\).

A graph \(G\) is \(\)-extendable if every edge is contained in a perfect matching of \(G\). In this note, we prove the following theorem. Let \(d \geq 3\) be an integer, and let \(G\) be a \(d\)-regular graph of order \(n\) without odd components. If \(G\) is not \(1\)-extendable, then \(n \geq 2d + 4\). Examples will show that the given bound is best possible.

A \(k\)-container \(C(u, v)\) of \(G\) between \(u\) and \(v\) is a set of \(k\) internally disjoint paths between \(u\) and \(v\). A \(k\)-container \(C(u,v)\) of \(G\) is a \(k^*\)-container if it contains all nodes of \(G\). A graph \(G\) is \(k^*\)-connected if there exists a \(k^*\)-container between any two distinct nodes. The spanning connectivity of \(G\), \(\kappa^*(G)\), is defined to be the largest integer \(k\) such that \(G\) is \(\omega^*\)-connected for all \(1 \leq \omega \leq k\) if \(G\) is an \(1^*\)-connected graph and undefined if otherwise. A graph \(G\) is super spanning connected if \(\kappa^*(G) = \kappa(G)\). In this paper, we prove that the \(n\)-dimensional augmented cube \(AQ_n\) is super spanning connected.

It is the aim of this paper to explore some new properties of the Padovan sequence using matrix methods. We derive new recurrence relations and generating matrices for the sums of Padovan numbers and \(4n\) subscripted Padovan sequences. Also, we define one type of \((0,1)\) upper Hessenberg matrix whose permanents are Padovan numbers.