The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph and named in honor of Professor Frank Harary. For a connected graph \(G = (V, E)\) with edge connectivity \(\lambda(G) \geq 2\), and an edge \(v_iv_j \in E(G)\), \(G – v_iv_j\) is the subgraph formed from \(G\) by deleting the edge \(v_iv_j\). Denote the Harary index of \(G\) and \(G – v_iv_j\) by \(H(G)\) and \(H(G – v_iv_j)\). Xu and Das [K.X. Xu, K.C. Das, On Harary index of graphs, Discrete Appl. Math. 159 (2011) 1631–1640] obtained lower and upper bounds on \(H(G + v_iv_j) – H(G)\) and characterized the equality cases in those bounds. We find that the equality case in the lower bound is not true and we correct it. In this paper, we give lower and upper bounds on \(H(G) – H(G – v_iv_j)\), and provide some graphs to satisfy the equality cases in these bounds. Furthermore, we extend the Harary index to directed graphs and obtain similar conclusions.

For a connected graph \(G\) of order \(n \geq 2\) and a linear ordering \(s: v_1, v_2, \ldots, v_n\) of \(V(G)\), define \(d(s) = \sum_{i=1}^{n-1} d(v_i, v_{i+1})\). The traceable number \(t(G)\) and upper traceable number \(t^+(G)\) of \(G\) are defined by \(t(G) = \min\{d(s)\}\) and \(t^+(G) = \max\{d(s)\}\), respectively, where the minimum and maximum are taken over all linear orderings \(s\) of \(V(G)\). Consequently, \(t(G) \leq t^+(G)\). It is known that \(n-1 \leq t(G) \leq 2n-4\) and \(n-1 \leq t^+(G) \leq \left\lfloor \frac{n^2}{2} \right\rfloor – 1\) for every connected graph \(G\) of order \(n \geq 3\) and, furthermore, for every pair \(n, A\) of integers with \(2n-1 \leq A \leq 2n-4\) there exists a graph of order \(n\) whose traceable number equals \(A\). In this work, we determine all pairs \(A, B\) of positive integers with \(A \leq B\) that are realizable as the traceable number and upper traceable number, respectively, of some graph. It is also determined for which pairs \(n, B\) of integers with \(n-1 \leq B \leq \left\lfloor \frac{n^2}{2} \right\rfloor – 1\) there exists a graph whose order equals \(n\) and upper traceable number equals \(\mu\).

A graph is \(1\)-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. A \(k\)-(p, 1)-total labelling of a graph \(G\) is a function \(f\) from \(V(G) \cup E(G)\) to the color set \(\{0, 1, \ldots, k\}\) such that \(|f(u) – f(v)| \geq 1\) if \(uv \in E(G)\), \(|f(e_1) – f(e_2)| \geq 1\) if \(e_1\) and \(e_2\) are two adjacent edges in \(G\), and \(|f(u) – f(e)| \geq p\) if the vertex \(u\) is incident to the edge \(e\). The minimum \(k\) such that \(G\) has a \(k-(p, 1)\)-total labelling, denoted by \(\lambda_p^T(G)\), is called the \((p, 1)\)-total labelling number of \(G\). In this paper, we prove that, if a 1-planar graph \(G\) satisfies that maximum degree \(\Delta(G) \geq 7p + 1\) and no adjacent triangles in \(G\) or maximum degree \(\Delta(G) \geq 6p + 3\) and no intersecting triangles in \(G\), then \(\lambda_p^T(G) \leq \Delta + 2p – 2\), \(p \geq 2\).

The hyper-star graph \(HS(n,k)\) is defined as follows: its vertex-set is the set of \(\{0, 1\}\)-sequences of length \(n\) with weight \(k\), where the weight of a sequence \(v\) is the number of \(1\)s in \(v\), and two vertices are adjacent if and only if one can be obtained from the other by exchanging the first symbol with a different symbol (\(1\) with \(0\), or \(0\) with \(1\)) in another position. In this paper, we will find the automorphism groups of regular hyper-star and folded hyper-star graphs. Then, we will show that only the graphs \(HS(4, 2)\) and \(FHS(4, 2)\) are Cayley graphs.

Let \(G_1\) and \(G_2\) be two connected graphs. The Kronecker product \(G_1 \times G_2\) has vertex set \(V(G_1 \times G_2) = V(G_1) \times V(G_2)\) and the edge set \(E(G_1 \times G_2) = \{(u_1, v_1), (u_2, v_2) : u_1u_2 \in E(G_1), v_1v_2 \in E(G_2)\}\). In this paper, we show that \(K_n \times K_m\) is super-\(\chi\) for \(n \geq m \geq 2\) and \(n+m \geq 5\), \(K_m \times P_n\) is super-\(\kappa\) for \(n \geq m \geq 3\), and \(K_m \times C_n\) is super-\(\kappa\) for \(n \geq m \geq 3\).

An explicit expression of the restricted edge connectivity of strong product of two triangle-free graphs is presented, which yields a sufficient and necessary condition for these strong product graphs to be super restricted edge connected.

The anti-Ramsey number \(AR(n,G)\), for a graph \(G\) and an integer \(n \geq |V(G)|\), is defined to be the minimal integer \(r\) such that in any edge-colouring of \(K_n\) by at least \(r\) colours there is a multicoloured copy of \(G\), namely, a copy of \(G\) whose edges have distinct colours. In this paper, we determine the anti-Ramsey numbers of all graphs having at most four edges.

In this paper, we determine the unique bicyclic graph with the largest signless Laplacian spectral radius among all the bicyclic graphs with \(n\) vertices and a given girth.

For a connected graph \(G\) and any two vertices \(u\) and \(v\) in \(G\), let \(d(u,v)\) denote the distance between \(u\) and \(v\) and let \(d(G)\) be the diameter of \(G\). For a subset \(S\) of \(V(G)\), the distance between \(v\) and \(S\) is \(d(v, S) = \min\{d(v,x) \mid x \in S\}\). Let \(\Pi = \{S_1, S_2, \ldots, S_k\}\) be an ordered \(k\)-partition of \(V(G)\). The representation of \(v\) with respect to \(\Pi\) is the \(k\)-vector \(r(v \mid \Pi) = (d(v, S_1), d(v, S_2), \ldots, d(v, S_k))\). A partition \(\Pi\) is a resolving partition for \(G\) if the \(k\)-vectors \(r(v \mid \Pi)\), \(v \in V(G)\) are distinct. The minimum \(k\) for which there is a resolving \(k\)-partition of \(V(G)\) is the partition dimension of \(G\), and is denoted by \(pd(G)\). A partition \(\Pi = \{S_1, S_2, \ldots, S_k\}\) is a resolving path \(k\)-partition for \(G\) if it is a resolving partition and each subgraph induced by \(S_i\), \(1 \leq i \leq k\), is a path. The minimum \(k\) for which there exists a path resolving \(k\)-partition of \(V(G)\) is the path partition dimension of \(G\), denoted by \(ppd(G)\). In this paper, path partition dimensions of trees and the existence of graphs with given path partition, partition, and metric dimension, respectively, are studied.

Let \(A\) be an abelian group with \(|A| \geq 4\). Suppose that \(G\) is a \(3\)-edge-connected simple graph on \(n \geq 19\) vertices. We show in this paper that if \(\max\{d(x), d(y), d(z)\} \geq n/6\) for every \(3\)-independent vertices \(\{x, y, z\}\) of \(G\), then either \(G\) is \(A\)-connected or \(G\) can be \(T\)-reduced to the Petersen graph, which generalizes the result of Zhang and Li (Graphs and Combin., \(30 (2014), 1055-1063).\)

Let \({F}_q\) be a finite field of odd order \(q\). In this note, the generator polynomials and the numbers of all self-dual and self-orthogonal cyclic and negacyclic codes of length \(2^m\) over \({F}_q\) are precisely characterized.

In this paper, we find the star chromatic number \(\chi_s\) for the central graph of sunlet graphs \(C(S_n)\), line graph of sunlet graphs \(L(S_n)\), middle graph of sunlet graphs \(M(S_n)\), and the total graph of sunlet graphs \(T(S_n)\).

Multireceiver authentication codes allow one sender to construct an authenticated message for a group of receivers such that each receiver can verify the authenticity of the received message. In this paper, we construct multireceiver authentication codes from pseudo-symplectic geometry over finite fields. The parameters and the probabilities of deceptions of the two codes are also computed.

For a simple undirected graph \(G\) with vertex set \(V\) and edge set \(E\), a total \(k\)-labeling \(\lambda: V \cup E \rightarrow \{1, 2, \ldots, k\}\) is called a vertex irregular total \(k\)-labeling of \(G\) if for every two distinct vertices \(x\) and \(y\) of \(G\), their weights \(wt(x)\) and \(wt(y)\) are distinct, where the weight of a vertex \(x\) in \(G\) is the sum of the label of \(x\) and the labels of all edges incident with the vertex \(x\). The total vertex irregularity strength of \(G\), denoted by \(\text{tus}(G)\), is the minimum \(k\) for which the graph \(G\) has a vertex irregular total \(k\)-labeling. The complete \(m\)-partite graph on \(n\) vertices in which each part has either \(\left\lfloor \frac{n}{m} \right\rfloor\) or \(\left\lceil \frac{n}{m} \right\rceil\) vertices is denoted by \(T_{n,m}\). The total vertex irregularity strength of some equitable complete \(m\)-partite graphs, namely, \(T_{m,m+1}\), \(T_{m,m+2}\), \(T_{m,2m}\), \(T_{m,2m+4}\), \(T_{3m-1}\) (\(m \geq 4\)), \(T_{n}\) (\(n = 3m+r\), \(r = 1, 2, \ldots, m-1\)), and equitable complete \(3\)-partite graphs have been studied in this paper.

Suppose \(m\) and \(t\) are integers such that \(0 < t \leq m\). An \((m,t)\)-splitting system is a pair \((X, \mathcal{B})\) that satisfies for every \(Y \subseteq X\) with \(|Y| = t\), there is a subset \(B\) of \(X\) in \(\mathcal{B}\), such that \(|B \cap Y| = \left\lfloor \frac{t}{2} \right\rfloor\) or \(|(X \setminus B) \cap Y| = \left\lceil \frac{t}{2} \right\rceil\). Suppose \(m\), \(t_1\), and \(t_2\) are integers such that \(t_1 + t_2 \leq m\). An \((m, t_1, t_2)\)-separating system is a pair \((X, \mathcal{B})\) which satisfies for every \(P \subseteq X\), \(Q \subseteq X\) with \(|P| = t_1\), \(|Q| = t_2\), and \(P \cap Q = \emptyset\), there exists a block \(B \in \mathcal{B}\) for which either \(P \subseteq B\), \(Q \cap B = \emptyset\) or \(Q \subseteq B\), \(P \cap B = \emptyset\). We will give some results on splitting systems and separating systems for \(t = 5\) and \(t = 6\).

Motivated by the recent work by Ramirez \([8]\), related to the bi-periodic Fibonacci sequences, here we introduce the bi-periodic incomplete Lucas sequences that gives the incomplete Lucas sequence as a special case. We also give recurrence relations and the generating function of these sequences. Also, we give a relation between bi-periodic incomplete Fibonacci sequences and bi-periodic incomplete Lucas sequences.

In this paper, we prove the \(q\)-log-convexity of Domb’s polynomials, which was conjectured by Sun in the study of series for powers of \(\pi\). As a result, we obtain the log-convexity of Domb’s numbers. Our proof is based on the \(q\)-log-convexity of Narayana polynomials of type \(B\) and a criterion for determining \(q\)-log-convexity of self-reciprocal polynomials.

Two Schwenk-like formulas about the signless Laplacian matrix of a graph are given, and thus it gives new tools for computing \(Q\)-
characteristic polynomials of graphs directly. As an application, we give the \(Q\)-characteristic polynomial of lollipop graphs and reprove the known result that no two non-isomorphic lollipop graphs are \(Q\)-cospectral by a simple manner.

In this paper, we give a general result which enlarge the class of graphs known to have \(\alpha\)-labeling.

An independent set in a graph \(G\) is a subset \(I\) of the vertices such that no two vertices in \(I\) are adjacent. We say that \(I\) is a maximum independent set in \(G\) if no other independent set is larger than \(I\). In this paper, we study the problem of determining the second and third largest number of maximum independent sets among all trees and forests. Extremal graphs achieving these values are also given.

This paper is motivated by the concept of the signed \(k\)-independence problem and dedicated to the complexity of the problem on graphs. We show that the problem is linear-time solvable for any strongly chordal graph with a strong elimination ordering and polynomial-time solvable for distance-hereditary graphs. For any fixed positive integer \(k \geq 1\), we show that the signed \(k\)-independence problem on chordal graphs and bipartite planar graphs is NP-complete. Furthermore, we show that even when restricted to chordal graphs or bipartite planar graphs, the signed \(k\)-independence problem, parameterized by a positive integer \(k\) and weight \(\kappa\), is not fixed-parameter tractable.

Edge minimal Hamilton laceable bigraphs on \(2m\) vertices have at least \(\left\lfloor \frac{m+3}{6} \right\rfloor\) vertices of degree \(2\). If a bigraph is edge minimal with respect to Hamilton laceability, it is by definition edge critical, meaning the deletion of any edge will cause it to no longer be Hamilton laceable. The converse need not be true. The \(m\)-crossed prisms \([8]\) on \(4m\) vertices are edge critical for \(m \geq 2\) but not edge minimal since they are cubic. A simple modification of \(m\)-crossed prisms forms a family of “sausage” bigraphs on \(4m + 2\) vertices that are also cubic and edge critical. Both these families share the unusual property that they have exponentially many Hamilton paths between every pair of vertices in different parts. Even so, since the bigraphs are edge critical, deleting an arbitrary edge results in at least one pair having none.

In this paper, we investigate some new identities of symmetry for the Carlitz \(q\)-Bernoulli polynomials invariant under \(S_4\), which are derived from \(p\)-adic \(q\)-integrals on \(\mathbb{Z}_p\).

In this paper, we give the definition of acyclic total coloring and acyclic total chromatic number of a graph. It is proved that the acyclic total chromatic number of a planar graph \(G\) with maximum degree \(\Delta(G)\) and girth \(g\) is at most \(\Delta(G)+2\) if \(\Delta \geq 12\), or \(\Delta \geq 6\) and \(g \geq 4\), or \(\Delta = 5\) and \(g \geq 5\), or \(g \geq 6\). Moreover, if \(G\) is a series-parallel graph with \(\Delta \geq 3\) or a planar graph with \(\Delta \geq 3\) and \(g \geq 12\), then the acyclic total chromatic number of \(G\) is \(\Delta(G) + 1\).

Let \(G\) be a graph and \(\pi(G, x)\) its permanental polynomial. A vertex-deleted subgraph of \(G\) is a subgraph \(G – v\) obtained by deleting from \(G\) vertex \(v\) and all edges incident to it. In this paper, we show that the derivative of the permanental polynomial of \(G\) equals the sum of permanental polynomials of all vertex-deleted subgraphs of \(G\). Furthermore, we discuss the permanental polynomial version of Gutman’s problem [Research problem \(134\), Discrete Math. \(88 (1991) 105–106\)], and give a solution.

A semigraph G is edge complete if every pair of edges in G are adjacent. In this paper, we enumerate the non isomorphic semigraphs in one type of edge complete \((p,3)\) semigraphs without isolated vertices.

In this paper, the \(\lambda\)-number of the circular graph \(C(km, m)\) is shown to be at most \(9\) where \(m \geq 3\) and \(k \geq 2\), and the \(\lambda\)-number of the circular graph \(C(km + s, m)\) is shown to be at most \(15\) where \(m \geq 3\), \(k \geq 2\), and \(1 \leq s \leq m-1\). In particular, the \(\lambda\)-numbers of \(C(2m, m)\) and \(C(n, 2)\) are determined, which are at most \(8\). All our results indicate that Griggs and Yeh’s conjecture holds for circular graphs. The conjecture says that for any graph \(G\) with maximum degree \(\Delta \geq 2\), \(\lambda(G) \leq \Delta^2\). Also, we determine \(\lambda\)-numbers of \(C(n, 3)\), \(C(n, 4)\), and \(C(n, 5)\) if \(n \equiv 0 \pmod{7}\).

In this paper, we generalize the notion of solid bursts from classical codes equipped with Hamming metric \([14]\) to array codes endowed with RT-metric \([13]\) and obtain some bounds on the parameters of RT-metric array codes for the correction and detection of solid burst array errors.

Given a graph \(G = (V,E)\), a matching \(M\) of \(G\) is a subset of \(E\), such that every vertex of \(V\) is incident to at most one edge of \(M\). A \(k\)-matching is a matching with \(k\) edges. The total number of matchings in \(G\) is used in chemoinformatics as a structural descriptor of a molecular graph. Recently, Vesalian and Asgari (MATCH Commun. Math. Comput. Chem. \(69 (2013) 33–46\)) gave a formula for the number of \(5\)-matchings in triangular-free and \(4\)-cycle-free graphs based on the degrees of vertices and the number of vertices, edges, and \(5\)-cycles. But, many chemical graphs are not triangular-free or \(4\)-cycle-free, e.g., boron-nitrogen fullerene graphs (or BN-fullerene graphs). In this paper, we take BN-fullerene graphs into consideration and obtain formulas for the number of \(5\)-matchings based on the number of hexagons.

This paper aims to provide a systematic investigation of the family of polynomials generated by the Rodrigues’ formulas
\[K_{n_1,n_2}^{(\alpha_1, \alpha_2)}(x, k,p) = (-1)^{n_1+n_2} e^{px^k}[\prod\limits_{j=1}^2x^{-\alpha}\frac{d^nj}{dx^{n_j}} (x)^{\alpha_j+n_j}]e^{-px^k},\]
and
\[M_{n_1,n_2}^{(\alpha_0,p_1,p_2)}(x, k) = \frac{(-1)^{n_1+n_2}}{p_1^{n_1}p_2^{p_2}}x^{-\alpha_0}[\prod\limits_ {j=1}^{2}e^{p_jx^k}\frac{d^nj}{dx^{n_j}}{dx^{n_j}}e^{-p_jx^k}]x^{n_1+n_2+\alpha_0},\]
These polynomials include the multiple Laguerre and the multiple Laguerre-Hahn polynomials, respectively. The explicit forms, certain operational formulas involving these polynomials with some applications, and linear generating functions for \(K_{n_1,n_2}^{(\alpha_1, \alpha_2)}(x, k,p)\) and \(M_{n_1,n_2}^{(\alpha_0,p_1,p_2)}(x, k)\) are obtained.

For an \(n\)-connected graph \(G\), the \(n\)-wide diameter \(d_n(G)\), is the minimum integer \(m\) such that there are at least \(n\) internally disjoint \((di)\)paths of length at most \(m\) between any vertices \(x\) and \(y\). For a given integer \(l\), a subset \(S\) of \(V(G)\) is called an \((l, n)\)-dominating set of \(G\) if for any vertex \(x \in V(G) – S\) there are at least \(n\) internally disjoint \((di)\)paths of length at most \(l\) from \(S\) to \(z\). The minimum cardinality among all \((l, n)\)-dominating sets of \(G\) is called the \((l, n)\)-domination number. In this paper, we obtain that the \((l, n)\)-domination number of the \(d\)-ary cube network \(C(d, n)\) is \(2\) for \(1 \leq w \leq d\) and \(d_w(G) – f(d, n) \leq l \leq d_w(G) – 1 \) if \(d,n\geq 4\), where \(f(d, n) = \min\{e(\left\lfloor \frac{n}{2} \right\rceil + 1), \left\lfloor \frac{n}{2} \right\rfloor e\}\).

Let \(k\) be a positive integer, and let \(G\) be a simple graph with vertex set \(V(G)\). A function \(f: V(G) \rightarrow \{-1, 1\}\) is called a signed \(k\)-dominating function if \(\sum_{u \in N(v)} f(u) \geq k\) for each vertex \(v \in V(G)\). A set \(\{f_1, f_2, \ldots, f_d\}\) of signed \(k\)-dominating functions on \(G\) with the property that \(\sum_{i=1}^{d} f_i(v) \leq 1\) for each \(v \in V(G)\), is called a signed \(k\)-dominating family (of functions) on \(G\). The maximum number of functions in a signed \(k\)-dominating family on \(G\) is the signed \(k\)-domatic number of \(G\), denoted by \(d_{kS}(G)\). In this paper, we initiate the study of signed \(k\)-domatic numbers in graphs and we present some sharp upper bounds for \(d_{kS}(G)\). In addition, we determine the signed \(k\)-domatic number of complete graphs.

In this paper, \(E_2\)-cordiality of a graph \(G\) is considered. Suppose \(G\) contains no isolated vertex, it is shown that \(G\) is \(E_2\)-cordial if and only if \(G\) is not of order \(4n + 2\).

A Hamiltonian walk of a connected graph \(G\) is a closed spanning walk of minimum length in \(G\). The length of a Hamiltonian walk in \(G\) is called the Hamiltonian number, denoted by \(h(G)\). An Eulerian walk of a connected graph \(G\) is a closed walk of minimum length which contains all edges of \(G\). In this paper, we improve some results in [5] and give a necessary and sufficient condition for \(h(G) < e(G)\). Then we prove that if two nonadjacent vertices \(u\) and \(v\) satisfying that \(\deg(u) + \deg(v) \geq |V(G)|\), then \(h(G) = h(G + uv)\). This result generalizes a theorem of Bondy and Chvatal for the Hamiltonian property. Finally, we show that if \(0 \leq k \leq n-2\) and \(G\) is a 2-connected graph of order \(n\) satisfying \(\deg(u) + \deg(v) + \deg(w) \geq \frac{3n+k-2}{2}\) for every independent set \(\{u,v,w\}\) of three vertices in \(G\), then \(h(G) \leq n+k\). It is a generalization of Bondy's result.

Let \(G\) be a finite abelian group of order \(n\). The barycentric Ramsey number \(BR(H,G)\) is the minimum positive integer \(r\) such that any coloring of the edges of the complete graph \(K_r\) by elements of \(G\) contains a subgraph \(H\) whose assigned edge colors constitute a barycentric sequence, i.e., there exists one edge whose color is the “average” of the colors of all edges in \(H\). When the number of edges \(e(H) \equiv 0 \pmod{\exp(G)}\), \(BR(H,G)\) are the well-known zero-sum Ramsey numbers \(R(H,G)\). In this work, these Ramsey numbers are determined for some graphs, in particular, for graphs with five edges without isolated vertices using \(G = \mathbb{Z}_n\), where \(2 \leq n \leq 4\), and for some graphs \(H\) with \(e(H) \equiv 0 \pmod{2}\) using \(G = \mathbb{Z}_2^s\).