Let \(G\) be a \(2\)-connected graph with maximum degree \(\Delta(G) \geq d\), and let \(x\) and \(z\) be distinct vertices of \(G\). Let \(W\) be a subset of \(V(G) \setminus \{x, z\}\) such that \(|W| \leq d – 1\). Hirohata proved that if \(\max\{d_G(u), d_G(v)\} \geq d\) for every pair of vertices \(u, v \in V(G) \setminus \{x, z\} \cup W\) such that \(d_G(u, v) = 2\), then \(x\) and \(z\) are joined by a path of length at least \(d – |W|\). In this paper, we show that if \(G\) satisfies the conditions of Hirohata’s theorem, then for any given vertex \(y\) such that \(d_G(y) \geq d\), \(x\) and \(z\) are joined by a path of length at least \(d – |W|\) which contains \(y\).

For any positive integer \(k\), there exists a smallest positive integer \(N\), depending on \(k\), such that every \(2\)-coloring of \(1, 2, \ldots, N\) contains a monochromatic solution of the equation \(x + y + kz = 3w\). Based on computer checks, Robertson and Myers in \([5]\) conjectured values for \(N\) depending on the congruence class of \(k\) (mod \(9\)). In this note, we establish the values of \(N\) and find that in some cases they depend on the congruence class of \(k\) (mod \(27\)).

The support of a matrix \(M\) is the \((0, 1)\)-matrix with \(ij\)-th entry equal to \(1\) if the \(ij\)-th entry of \(M\) is non-zero, and equal to \(0\), otherwise. The digraph whose adjacency matrix is the support of \(M\) is said to be the digraph of \(M\). In this paper, we observe some general properties of digraphs of unitary matrices.

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.