The total chromatic number \(\chi_\tau(G)\) is the least number of colours needed to colour the vertices and edges of a graph \(G\) such that no incident or adjacent elements (vertices or edges) receive the same colour. This work determines the total chromatic number of grids, particular cases of partial grids, near-ladders, and of \(k\)-dimensional cubes.

The \({star arboricity}\) \(sa(G)\) of a graph \(G\) is the minimum number of star forests which are needed to decompose all edges of \(G\). For integers \(k\) and \(n\), \(1 \leq k \leq n\), the \({crown}\) \(C_{n,k}\) is the graph with vertex set \(\{a_0, a_1, \ldots, a_{n-1}, b_0, b_1, \ldots, b_{n-1}\}\) and edge set \(\{a_ib_j : i = 0, 1, \ldots, n-1, j \equiv i+1, i+2, \ldots, i+k \pmod{n}\}\). In \([2]\), Lin et al. conjectured that for every \(k\) and \(n\), \(3 \leq k \leq n-1\), the star arboricity of the crown \(C_{n,k}\) is \(\lceil k/2 \rceil + 1\) if \(k\) is odd and \(\lceil k/2 \rceil + 2\) otherwise. In this note, we show that the above conjecture is not true for the case \(n = 9t\) (\(t\) is a positive integer) and \(k = 4\) by showing that \(sa(C_{9t,4}) = 3\).

Let \(\mathcal{P}(n,k)\) denote the number of graphs on \(n+k\) vertices that contain \(P_n\), a path on \(n\) vertices, as an induced subgraph. In this note, we will find upper and lower bounds for \(\mathcal{P}(n,k)\). Using these bounds, we show that for \(k\) fixed, \(\mathcal{P}(n,k)\) behaves roughly like an exponential function of \(n\) as \(n\) gets large.

A \({dominating \;broadcast}\) of a graph \(G\) of diameter \(d\) is a function \(f: V(G) \to \{0, 1, 2, \ldots, d\}\) such that for all \(v \in V(G)\) there exists \(u \in V(G)\) with \(d(u, v) \leq f(u)\). We investigate dominating broadcasts for caterpillars.

In this paper, we obtain a fundamental result on the dynamical behavior of symmetric weighted mappings for two-dimensional real sequence spaces \({R}_s\).

In \(2006\), Mojdeh and Jafari Rad [On the total domination critical graphs, Electronic Notes in Discrete Mathematics, 24 (2006), 89-92] gave an open problem: Does there exist a \(3\)-\(\gamma_t\)-critical graph \(G\) of order \(\Delta(G) + 3\) with \(\Delta(G)\) odd and \(\delta(G) \geq 2\)? In this paper, we positively answer that for each odd integer \(n \geq 9\), there exists a \(3\)-\(\gamma_t\)-critical graph \(G_n\) of order \(n+3\) with \(\delta(G) \geq 2\). On the contrary, we also prove that for \(\Delta(G) = 3, 5, 7\), there is no \(3\)-\(\gamma_t\)-critical graph of order \(\Delta(G) + 3\) with \(\delta(G) \geq 2\).

Let \(\{w_n\}\) be a second-order recurrence sequence. According to the definition and characteristics of the recurrent sequence, we proved a recursion formula for certain reciprocal sums whose denominators are products of consecutive elements of \(\{w_n\}\).

Let \(G\) be a graph in which each vertex has been colored using one of \(k\) colors, say \(c_1, c_2, \ldots, c_k\). If an \(m\)-cycle \(C\) in \(G\) has \(n_i\) vertices colored \(c_i\), \(i = 1, 2, \ldots, k\), and \(|n_i – n_j| \leq 1\) for any \(i, j \in \{1, 2, \ldots, k\}\), then \(C\) is equitably \(k\)-colored. An \(m\)-cycle decomposition \(\mathcal{C}\) of a graph \(G\) is equitably \(k\)-colorable if the vertices of \(G\) can be colored so that every \(m\)-cycle in \(\mathcal{C}\) is equitably \(k\)-colored. For \(m = 4, 5\), and \(6\), we completely settle the existence problem for equitably \(2\)-colorable \(m\)-cycle decompositions of complete graphs with the edges of a \(1\)-factor added.

Suppose a network facility location problem is modelled by means of an undirected, simple graph \(G = (\mathcal{V, E})\) with \(\mathcal = \{v_1, \ldots, v_n\}\). Let \(\mathbf{r} = (r_1, \ldots, r_n)\) and \(\mathbf{s} = (s_1, \ldots, s_n)\) be vectors of nonnegative integers and consider the combinatorial optimization problem of locating the minimum number, \(\gamma(\mathbf{r}, \mathbf{s}, G)\) (say), of commodities on the vertices of \(G\) such that at least \(s_j\) commodities are located in the vicinity of (i.e. in the closed neighbourhood of) vertex \(v_j\), with no more than \(r_j\) commodities placed at vertex \(v_j\) itself, for all \(j = 1, \ldots, n\). In this paper we establish lower and upper bounds on the parameter \(\gamma(\mathbf{r}, \mathbf{s}, G)\) for a general graph \(G\). We also determine this parameter exactly for certain classes of graphs, such as paths, cycles, complete graphs, complete bipartite graphs and establish good upper bounds on \(\gamma(\mathbf{r}, \mathbf{s}, G)\) for a class of grid graphs in the special case where \(r_j = r\) and \(s_j = s\) for all \(j = 1, \ldots, n\).

Let \(A\) be an arbitrary circulant stochastic matrix, and let \(\underline{x}_0\) be a vector. An “asymptotic” canonical form is derived for \(A^k\) (as \(k \to \infty\)) as a tensor product of three simple matrices by employing a pseudo-invariant on sections of states for a Markov process with transition matrix \(A\), and by analyzing how \(A\) acts on the sections, through its auxiliary polynomial. An element-wise asymptotic characterization of \(A^k\) is also given, generalizing previous results to cover both periodic and aperiodic cases. For a particular circulant stochastic matrix, identifying the intermediate stage at which fractions first appear in the sequence \(\underline{x}_k = A^k \underline{x}_0\), is accomplished by utilizing congruential matrix identities and \((0,1)\)-matrices to determine the minimum \(2\)-adic order of the coordinates of \(\underline{x}_k\), through their binary expansions. Throughout, results are interpreted in the context of an arbitrary weighted average repeatedly applied simultaneously to each term of a finite sequence when read cyclically.