The \(k\)-restricted total domination number of a graph \(G\) is the smallest integer \(t_k\), such that given any subset \(U\) of \(k\) vertices of \(G\), there exists a total dominating set of \(G\) of cardinality at most \(t\), containing \(U\). Hence, the \(k\)-restricted total domination number of a graph \(G\) measures how many vertices are necessary to totally dominate a graph if an arbitrary set of \(k\) vertices are specified to be in the set. When \(k = 0\), the \(k\)-restricted total domination number is the total domination number. For \(1 \leq k \leq n\), we show that \(t_k \leq 4(n + k)/7\) for all connected graphs of order \(n\) and minimum degree at least two and we characterize the graphs achieving equality. These results extend earlier results of the author (J. Graph Theory \(35 (2000), 21-45)\). Using these results we show that if \(G\) is a connected graph of order \(n\) with the sum of the degrees of any two adjacent vertices at least four, then \(\gamma_t(G) \leq 4n/7\) unless \(G \in \{C_3, C_5, C_6, C_{10}\}\).

The Szeged index of a graph \(G\) is defined as \(\text{Sz}(G) = \sum_{e=uv \in E(G)} N_u(e|G) N_v(e|G)\), where \(N_u(e|G)\) is the number of vertices of \(G\) lying closer to \(u\) than to \(v\) and \(N_v(e|G)\) is the number of vertices of \(G\) lying closer to \(v\) than to \(u\). In this article, the Szeged index of some hexagonal systems applicable in nanostructures is computed.

In this paper, we consider the class of impartial combinatorial games for which the set of possible moves strictly decreases. Each game of this class can be considered as a domination game on a certain graph, called the move-graph. We analyze this equivalence for several families of combinatorial games, and introduce an interesting graph operation called iwin and match that preserves the Grundy value. We then study another game on graphs related to the dots and boxes game, and we propose a way to solve it.

Let \(C_n\) denote the cycle with \(n\) vertices, and \(C_n^{(t)}\) denote the graphs consisting of \(t\) copies of \(C_n\), with a vertex in common. Koh et al. conjectured that \(C_n^{(t)}\) is graceful if and only if \(nt \equiv 0,3 \pmod{4}\). The conjecture has been shown true for \(n = 3,5,6,7,9,11,4k\). In this paper, the conjecture is shown to be true for \(n = 13\).

This paper deals with a connection between the universal circuits matrix \([10]\) and the crossing relation \([1,5]\). The value of the universal circuits matrix obtained for \(\overline{\omega}\), where \(\omega\) is an arbitrary feedback function that generates de Bruijn sequences, forms the binary matrix that represents the crossing relation of \(\omega\). This result simplifies the design and study of the feedback functions that generate the de Bruijn sequences and allows us to decipher many inforrnations about the adjacency graphs of another feedback functions. For example, we apply these results to analyze the Hauge-Mykkeltveit classification of a family of de Bruijn sequences \([4]\).

In a given graph \(G\), a set \(S\) of vertices with an assignment of colors is a defining set of the vertex coloring of \(G\), if there exists a unique extension of the colors of \(S\) to a \(\chi(G)\)-coloring of the vertices of \(G\). A defining set with minimum cardinality is called a smallest defining set (of vertex coloring) and its cardinality, the defining number, is denoted by \(d(G, \chi)\). Let \(d(n, r, \chi = k)\) be the smallest defining number of all \(r\)-regular \(k\)-chromatic graphs with \(n\) vertices. Mahmoodian \(et.\; al [7]\) proved that, for a given \(k\) and for all \(n \geq 3k\), if \(r \geq 2(k-1)\) then \(d(n, r, \chi = k) = k-1\). In this paper we show that for a given \(k\) and for all \(n < 3k\) and \(r \geq 2(k – 1)\), \(d(n, r, \chi = k) = k-1\).

A two-colored digraph \(D\) is primitive if there exist nonnegative integers \(h\) and \(k\) with \(h+k > 0\) such that for each pair \((i,j)\) of vertices there exists an \((h, k)\)-walk in \(D\) from \(i\) to \(j\). The exponent of the primitive two-colored digraph \(D\) is the minimum value of \(h + k\) taken over all such \(h\) and \(k\). In this paper, we consider the exponents of families of two-colored digraphs of order \(n\) obtained by coloring the digraph that has the exponent \((n – 1)^2\). We give the tight upper bound on the exponents, and the characterization of the extremal two-colored digraph.

A graceful labeling of a graph \(G\) with \(m\) edges is a function \(f: V(G) \to \{0, \ldots, m\}\) such that distinct vertices receive distinct numbers and \(\{|f(u) – f(v)|: uv \in E(G)\} = \{1, \ldots, m\}\). A graph is graceful if it has a graceful labeling. In \([1]\) this question was posed: “Is there an \(n\)-chromatic graceful graph for \(n \geq 6\)?”. In this paper it is shown that for any natural number \(n\), there exists a graceful graph \(G\) with \(\chi(G) = n\).

A connected graph \(G = (V, E)\) is said to be \((a, d)\)-antimagic, for some positive integers \(a\) and \(d\), if its edges admit a labeling by all the integers in the set \(\{1, 2, \ldots, |E(G)|\}\) such that the induced vertex labels, obtained by adding all the labels of the edges adjacent to each vertex, consist of an arithmetic progression with the first term \(a\) and the common difference \(d\). Mirka Miller and Martin Ba\'{e}a proved that the generalized Petersen graph \(P(n, 2)\) is \((\frac{3n+3}{2}, 3)\)-antimagic for \(n \equiv 0 \pmod{4}\), \(n \geq 8\) and conjectured that \(P(n, k)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for even \(n\) and \(2 \leq k \leq \frac{n}{2}-1\). The first author of this paper proved that \(P(n, 3)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for even \(n \geq 6\). In this paper, we show that the generalized Petersen graph \(P(n, 2)\) is \((\frac{3n+6}{2} , 3)\)-antimagic for \(n \equiv 2 \pmod{4}\), \(n \geq 10\).

Let \(0 \leq p \leq [\frac{r+1}{2}]\) and \(\sigma(K_{r+1}^{-p},n)\) be the smallest even integer such that each \(n\)-term graphic sequence with term sum at least \(\sigma(K_{r+1}^{-p},n)\) has a realization containing \(K_{r+1}^{-p}\) as a subgraph, where \(K_{r+1}^{-p}\) is a graph obtained from a complete graph \(K_{r+1}\) on \(r+1\) vertices by deleting \(p\) edges which form a matching. In this paper, we determine \(\sigma(K_{r+1}^{-p},n)\) for \(r \geq 2, 1 \leq p \leq [\frac{r+1}{2}]\) and \(n \geq 3r + 3\). As a corollary, we also determine \(\sigma(K_{1^*,2^t}n)\) for \(t \geq 1\) and \(n \geq 3s + 6t\), where \(K_{1^*,2^t}\) is an \(r_1\times r_2\times \ldots \times r_{s+t}\) complete \((s + t)\)-partite graph with \(r_1 = r_2 = \ldots = r_s = 1\) and \(r_{s+1} = r_{s+2} = \ldots = r_{s+t} = 2\) and \(\sigma(K_{1^*,2^t},n)\) is the smallest even integer such that each \(n\)-term graphic sequence with term sum at least \(\sigma(K_{1^*,2^t},n)\) has a realization containing \(K_{1^*,2^t}\) as a subgraph.