For two vertices \(u\) and \(v\) of a nontrivial connected graph \(G\), the set \(I[u,v]\) consists of all vertices lying on some \(u-v\) geodesic in \(G\), including \(u\) and \(v\). For \(S \subseteq V(G)\), the set \(Z[S]\) is the union of all sets \(I[u,v]\) for \(u,v \in S\). A set \(S \subseteq V(G)\) is a connected geodetic set of \(G\) if \(Z[S] = V(G)\) and the subgraph in \(G\) induced by \(S\) is connected. The minimum cardinality of a connected geodetic set of \(G\) is the connected geodetic number \(g_c(G)\) of \(G\) and a connected geodetic set of \(G\) whose cardinality equals \(g_c(G)\) is a minimum connected geodetic set of \(G\). A subset \(T\) of a minimum connected geodetic set \(S\) is a forcing subset for \(S\) if \(S\) is the unique minimum connected geodetic set of \(G\) containing \(T\). The forcing connected geodetic number \(f(S)\) of \(S\) is the minimum cardinality of a forcing subset of \(S\) and the forcing connected geodetic number \(f(G)\) of \(G\) is the minimum forcing connected geodetic number among all minimum connected geodetic sets of \(G\). Therefore, \(0 \leq f_c(G) \leq g_c(G)\). We determine all pairs \((a,b)\) of integers such that \(f_c(G) = a\) and \(gc(G) = b\) for some nontrivial connected graph \(G\). We also consider a problem of realizable triples of integers.

Hovey [11] called a graph \(G\) \(A\)-cordial, where \(A\) is an additive Abelian group, and \(f: V(G) \to A\) is a labeling of the vertices of \(G\) with elements of \(A\) such that when the edges of \(G\) are labeled by the induced labeling \(f: E(G) \to A\) by \(f^*(xy) = f(x) + f(y)\), then the number of vertices (resp. edges) labeled with \(\alpha\) and the number of vertices (resp. edges) labeled with \(\beta\) differ by at most one for all \(\alpha, \beta \in A\). When \(A = \mathbb{Z}_k\), we call a graph \(G\) \(k\)-cordial instead of \(\mathbb{Z}_k\)-cordial. In this paper, we give a sufficient condition for the join of two \(k\)-cordial graphs to be \(k\)-cordial and we give also a necessary condition for certain Eulerian graphs to be \(k\)-cordial when \(k\) is even, and finally we complete the characterization of the \(4\)-cordiality of the complete tripartite graph.

Let \(*\) be a binary graph operation. We call \(*\) a Cayley operation if \(\Gamma_1 * \Gamma_2\) is a Cayley graph for any two Cayley graphs \(\Gamma_1\) and \(\Gamma_2\) . In this paper, we prove that the Cartesian, (categorical or tensor) direct, and lexicographic products are Cayley operations. We also investigate the following question: Under what conditions on a binary graph operation \(*\) and Cayley graphs \(\Gamma_1\) and \(\Gamma_2\), the graph product \(\Gamma_1 * \Gamma_2\) is again a Cayley graph. The latter question is studied for the union, join (sum), replacement, and zig-zag products of graphs.

Let \(R(G)\) be the graph obtained from \(G\) by adding a new vertex corresponding to each edge of \(G\) and by joining each new vertex to the end vertices of the corresponding edge. Let \(RT(G)\) be the graph obtained from \(R(G)\) by adding a new edge corresponding to every vertex of \(G\), and by joining the end vertices of each new edge to the corresponding vertex of \(G\). In this paper, we determine the Laplacian polynomials of \(RT(G)\) of a regular graph \(G\). Moreover, we derive formulae and lower bounds of Kirchhoff indices of the graphs. Finally, we also present the formulae for calculating the Kirchhoff indices of some special graphs as applications, which show the correction and efficiency of the proposed results.

For integer \(n \geq 2\), let \(a_1, a_2, a_3, \ldots, a_n\) be an increasing sequence of nonnegative integers, and define the \(n\)-star \(St(a_1, a_2, \ldots, a_n)\) as the disjoint union of the \(n\) star graphs \(K(1, a_1), K(1, a_2), \ldots, K(1, a_n)\). In this paper, we have partially settled the conjecture by Lee and Kong [4] that says for any odd \(n \geq 3\), the \(n\)-star \(St(a_1, a_2, \ldots, a_n)\) is super edge magic. We solve the two cases:

1. The \(n\)-star \(St(a_1, a_2, \ldots, a_n)\) is super edge magic where \(a_i = 1 + (i – 1)d\) for all integers \(1 \leq i \leq n\) and \(d\) is any positive integer.

2. An \(n\)-star \(St(a_1, a_2, \ldots, a_n)\) is not super edge magic when \(a_1 = 0\).

Let \(G\) be a simple connected graph with the vertex set \(V(G)\). The eccentric distance sum of \(G\) is defined as \(\xi^d(G) = \sum_{v \in V(G)} \varepsilon(v) D_G(v)\), where \(\varepsilon(v)\) is the eccentricity of the vertex \(v\) and \(D_G(v)\) is the sum of all distances from the vertex \(v\). The Harary index of \(G\) is defined as \(H(G) = \sum_{u,v \in V(G)} \frac{1}{d(u, v)}\), where \(d(u, v)\) is the distance between \(u\) and \(v\) in \(G\). The degree powers of \(G\) is defined as \(H(G) = \sum_{|u,v| \subseteq V(G)} \frac{1}{d(u,v)}\) for the natural number \(p \geq 1\). In this paper, we determine the extremal graphs with the minimal eccentric distance sum, the maximal Harary index, and the maximal degree powers among all graphs with given diameter.

Let \(\Gamma(V, E)\) be a graph of order \(n\), \(S \subset V\), and let \(B(S)\) be the set of vertices in \(V \setminus S\) that have a neighbor in \(S\). The differential of a set \(S\) is defined as \(\partial(S) = |B(S)| – |S|\), and the differential of the graph \(\Gamma\) is defined as \(\partial(\Gamma) = \max\{\partial(S) : S \subset V\}\). In this paper, we obtain several tight bounds for the differential in Cartesian product graphs. In particular, we relate the differential in Cartesian product graphs with some known parameters of \(\Gamma_1 \times \Gamma_2\), namely, its domination number, its maximum and minimum degree, and its order. Furthermore, we compute explicitly the differential of some classes of product graphs.

The necessary and sufficient conditions for a given sequence of positive integers \(d_1, d_2, \ldots, d_n\) to be the degree sequence of \(3\)-connected graphs and cactus graphs are proved respectively by S. L. Hakimi [5] and A. R. Rao [6]. In this note, we utilize these results to prove a formula for the functions \(d_{tc}(2m)\) and \(d_{ca}(2m)\), the number of degree sequences with degree sum \(2m\) by \(3\)-connected graphs and cactus graphs respectively. We give generating function proofs and elementary proofs of the formulas \(d_{tc}(2m)\) and \(d_{ca}(2m)\).

In this paper, the graphs with maximal (signless Laplacian) spectral radius among all connected graphs with given matching number are characterized.

Let \(c\) be a proper \(k\)-coloring of a connected graph \(G\) and \(\Pi = (V_1, V_2, \ldots, V_k)\) be an ordered partition of \(V(G)\) into the resulting color classes. For a vertex \(v\) of \(G\), the color code of \(v\) with respect to \(\Pi\) is defined to be the ordered \(k\)-tuple \(c_\Pi := (d(v, V_1), d(v, V_2), \ldots, d(v, V_k))\), where \(d(v, V_i) = \min\{d(v, x) \mid x \in V_i\}\) for \(1 \leq i \leq k\). If distinct vertices have distinct color codes, then \(c\) is called a locating coloring. The minimum number of colors needed in a locating coloring of \(G\) is the locating chromatic number of \(G\), denoted by \(\chi_L(G)\). In this paper, we study the locating chromatic numbers of grids, the cartesian product of paths and complete graphs, and the cartesian product of two complete graphs.