Consider the following problem: Given a transitive tournament \(T\) of order \(n \geq 3\) and an integer \(k\) with \(1 \leq k \leq \binom{n}{2}\), which \(k\) ares in \(T\) should be reversed so that the resulting tournament has the largest number of spanning cycles? In this note, we solve the problem when \(7\) is sufficiently large compared to \(k\).

The bondage number \(b(G)\) of a graph \(G\) is the smallest number of edges whose removal results in a graph with domination number greater than the domination number of \(G\). Kang and Yuan [Bondage number of planar graphs. Discrete Math. \(222 (2000), 191-198]\) proved \(b(G) \leq \min\{8, \Delta + 2\}\) for every connected planar graph \(G\), where \(\Delta\) is the maximum degree of \(G\). Later Carlson and Develin [On the bondage number of planar and directed graphs. Discrete Math. \(306 (8-9) (2006), 820-826]\) presented a method to give a short proof for this result. This paper applies this technique to generalize the result of Kang and Yuan to any connected graph with crossing number less than four.

A \({Roman \;domination \;function}\) on a graph \(G = (V, E)\) is a function \(f: V(G) \to \{0, 1, 2\}\) satisfying the condition that every vertex \(u\) with \(f(u) = 0\) is adjacent to at least one vertex \(v\) with \(f(v) = 2\). The \({weight}\) of a Roman domination function \(f\) is the value \(f(V(G)) = \sum_{u \in V(G)} f(u)\). The minimum weight of a Roman dominating function on a graph \(G\) is called the \({Roman \;domination \;number}\) of \(G\), denoted by \(\gamma_R(G)\). In this paper, we study the Roman domination number of generalized Petersen graphs \(P(n, 2)\) and prove that \(\gamma_R(P(n, 2)) = \left\lceil \frac{8n}{7} \right\rceil (n\geq5)\).

Let \(G = (V, E)\) be a simple undirected graph. For an edge \(e\) of \(G\), the \({closed\; edge-neighborhood}\) of \(e\) is the set \(N[e] = \{e’ \in E \mid e’ \text{ is adjacent to } e\} \cup \{e\}\). A function \(f: E \to \{1, -1\}\) is called a signed edge domination function (SEDF) of \(G\) if \(\sum_{e’ \in N[e]} f(e’) > 1\) for every edge \(e\) of \(G\). The signed edge domination number of \(G\) is defined as \(\gamma’_s(G) = \min \left\{ \sum_{e \in E} |f(e)| \mid f \text{ is an SEDF of } G \right\}\). In this paper, we determine the signed edge domination numbers of all complete bipartite graphs \(K_{m,n}\), and therefore determine the signed domination numbers of \(K_m \times K_n\).

We discuss the primality of some corona graphs and some families of graphs.

An injective coloring of a graph \(G\) is an assignment of colors to the vertices of \(G\) so that any two vertices with a common neighbor receive distinct colors. A graph \(G\) is said to be injectively \(k\)-choosable if any list \(L(v)\) of size at least \(k\) for every vertex \(v\) allows an injective coloring \(\phi(v)\) such that \(\phi(v) \in L(v)\) for every \(v \in V(G)\). The least \(k\) for which \(G\) is injectively \(k\)-choosable is the injective choosability number of \(G\), denoted by \(\chi_i^l(G)\). In this paper, we obtain new sufficient conditions to ensure \(\chi_i^l(G) \leq \Delta(G) + 1\). We prove that if \(mad(G) \leq \frac{12k}{4k+3}\), then \(\chi_i^l(G) = \Delta(G) + 1\) where \(k = \Delta(G)\) and \(k \geq 4\). Typically, proofs using the discharging technique are different depending on maximum average degree \(mad(G)\) or maximum degree \(\Delta(G)\). The main objective of this paper is finding a function \(f(\Delta(G))\) such that \(\chi_i^l(G) \leq \Delta(G) + 1\) if \(mad(G) < f(\Delta(G))\), which can be applied to every \(\Delta(G)\).

The traditional parameter used as a measure of vulnerability of a network modeled by a graph with perfect nodes and edges that may fail is edge connectivity \(\lambda\). For the complete bipartite graph \(K_{p,q}\), where \(1 \leq p \leq q\), \(\lambda(K_{p,q}) = p\). In this case, failure of the network means that the surviving subgraph becomes disconnected upon the failure of individual edges. If, instead, failure of the network is defined to mean that the surviving subgraph has no component of order greater than or equal to some preassigned number \(k\), then the associated vulnerability parameter, the component order edge connectivity \(\lambda_c^{(k)}\), is the minimum number of edges required to fail so that the surviving subgraph is in a failure state. We determine the value of \(\lambda_c^{(k)}(K_{p,q})\) for arbitrary \(1 \leq p \leq q\) and \(4 \leq k \leq p+q\). As it happens, the situation is relatively simple when \(p\) is small and more involved when \(p\) is large.

A \(T\)-shape tree \(T(l_1, l_2, l_3)\) is obtained from three paths \(P_{l_1+1}\), \(P_{l_2+1}\), and \(P_{l_3+1}\) by identifying one of their pendent vertices. A generalized \(T\)-shape tree \(T_s(l_1, l_2, l_3)\) is obtained from \(T(l_1, l_2, l_3)\) by appending two pendent vertices to exactly \(s\) pendent vertices of \(T(l_1, l_2, l_3)\), where \(1 \leq s \leq 3\) is a positive integer. In this paper, we firstly show that the generalized \(T\)-shape tree \(T_2(l_1, l_2, l_3)\) is determined by its Laplacian spectrum. Applying similar arguments for the trees \(T_1(2l_1, l_2, l_3)\) and \(T_3(l_1, 2l_2, l_3)\), one can obtain that any generalized \(T\)-shape tree on \(n\) vertices is determined by its Laplacian spectrum.