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