The notation \(tK_3\) represents a graph with \(t\) copies of the complete graph \(K_3\). In this note, we discuss the goodness of path \(P_n\) or cycle \(C_n\) with respect to \(tK_3\). Furthermore, this result provides the computation of Ramsey number \(R(G, tK_3)\) when \(G\) is a set of disjoint paths or cycles.

A \(k\)-king in a digraph \(D\) is a vertex which can reach every other vertex by a directed path of length at most \(k\). Every tournament with no vertex of in-degree zero has at least three \(2\)-kings. In this paper, we present the structure of tournaments which have exactly three \(2\)-kings and prove that every strong tournament, containing at least \(k+2\) vertices with \(k \geq 3\), has at least \(k+1\) \(k\)-kings.

A kernel in a directed graph \(D(V, E)\) is a set \(S\) of vertices of \(D\) such that no two vertices in \(S\) are adjacent and for every vertex \(u\) in \(V \setminus S\) there is a vertex \(v\) in \(S\), such that \((u,v)\) is an arc of \(D\). The definition of kernel implies that the vertices in the kernel form an independent set. If the vertices of the kernel induce an independent set of edges, we obtain a variation of the definition of the kernel, namely a total-kernel. The problem of existence of a kernel is itself an NP-complete problem for a general digraph. But in this paper, we solve the strong total-kernel problem of an oriented Circular Ladder and Möbius Ladder in polynomial time.

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.