Let \(X = (V,E)\) be a digraph. \(X\) is maximally connected if \(\kappa(X) = \delta(X)\). \(X\) is maximally arc-connected if \(\lambda(X) = \delta(X)\). And \(X\) is super arc-connected if every minimum arc-cut of \(X\) is either the set of inarcs of some vertex or the set of outarcs of some vertex. In this paper, we prove that the strongly connected Bi-Cayley digraphs are maximally connected and maximally arc-connected, and most strongly connected Bi-Cayley digraphs are super arc-connected.

A \(2\)-rainbow dominating function (2RDF) of a graph \(G\) is a function \(f\) from the vertex set \(V(G)\) to the set of all subsets of the set \(\{1,2\}\) such that for any vertex \(v \in V(G)\) with \(f(v) = \emptyset\), the condition that there exists \(u \in N(v)\) with \(\bigcup_{u\in N(v)}f(u) = \{1,2\}\) is fulfilled, where \(N(v)\) is the open neighborhood of \(v\). A rainbow dominating function \(f\) is said to be a rainbow restrained domination function if the induced subgraph of \(G\) by the vertices with label \(\emptyset\) has no isolated vertex. The weight of a rainbow restrained dominating function is the value \(w(f) = \sum_{u \in V(G)} |f(u)|\). The minimum weight of a rainbow restrained dominating function of \(G\) is called the rainbow restrained domination number of \(G\). In this paper, we initiate the study of the rainbow restrained domination number and we present some bounds for this parameter.

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.