An edge coloring of a graph is called \({square-free}\) if the sequence of colors on certain walks is not a square, that is not of the form \(x_1, \ldots, x_m, x_{1}, \ldots, x_m\) for any \(m \in \mathbb{N}\). Recently, various classes of walks have been suggested to be considered in the above definition. We construct graphs, for which the minimum number of colors needed for a square-free coloring is different if the considered set of walks vary, solving a problem posed by Brešar and Klavžar. We also prove the following: if an edge coloring of \(G\) is not square-free (even in the most general sense), then the length of the shortest square walk is at most \(8|E(G)|^2\). Hence, the necessary number of colors for a square-free coloring is algorithmically computable.

If \(x\) is a vertex of a digraph \(D\), then we denote by \(d^+ (x)\) and \(d^- (x)\) the outdegree and the indegree of \(x\), respectively. The global irregularity of a digraph \(D\) is defined by \(i_g(D) = \max\{d^+ (x),d^- (x)\} – \min\{d^+ (y), d^- (y)\}\) over all vertices \(x\) and \(y\) of \(D\) (including \(x = y\)).

A \(c\)-partite tournament is an orientation of a complete \(c\)-partite graph. Recently, Volkmann and Winzen \([9]\) proved that \(c\)-partite tournaments with \(i_g(D) = 1\) and \(c \geq 3\) or \(i_g(D) = 2\) and \(c \geq 5\) contain a Hamiltonian path. Furthermore, they showed that these bounds are best possible.

Now, it is a natural question to generalize this problem by asking for the minimal value \(g(i,k)\) with \(i,k \geq 1\) arbitrary such that all \(c\)-partite tournaments \(D\) with \(i_g(D) \leq i\) and \(c \geq g(i,k)\) have a path covering number \(pc(D) \leq k\). In this paper, we will prove that \(4i-4k \leq g(i,k) \leq 4i-3k-1\), when \(i \geq k+2\). Especially in the case \(k = 1\), this yields that \(g(i, 1) = 4i-4\), which means that all \(c\)-partite tournaments \(D\) with the global irregularity \(i_g(D) = i\) and \(c \geq 4i-4\) contain a Hamiltonian path.

In this paper, we discuss a problem on packing a unit cube with smaller cubes, which is a generalization of one of Erdős’ favorite problems: the square-packing problem. We first give the definition of the packing function \(f_3(n)\), then give the bounds for \(f_3(n)\).

A set \(S\) of vertices in a graph \(G = (V, E)\) is a restrained dominating set of \(G\) if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V \setminus S\). The graph \(G\) is called restrained domination excellent if every vertex belongs to some minimum restrained dominating set of \(G\). We provide a characterization of restrained domination excellent trees.

In this paper, \(q\)-analogues of the Pascal matrix and the symmetric Pascal matrix are studied. It is shown that the \(q\)-Pascal matrix \(\mathcal{P}_n\) can be factorized by special matrices and the symmetric \(q\)-Pascal matrix \(\mathcal{Q}_n\) has the LDU-factorization and the Cholesky factorization. As byproducts, some \(q\)-binomial identities are produced by linear algebra. Furthermore, these matrices are generalized in one or two variables, where a short formula for all powers of \(q\)-Pascal functional matrix \(\mathcal{P}_n[x]\) is given. Finally, it is similar to Pascal functional matrix, we have the exponential form for \(q\)-Pascal functional matrix.

We view a lobster in this paper as below. A lobster with diameter at least five has a unique path \(H = x_0, x_1, \ldots, x_m\) with the property that, besides the adjacencies in \(H\), both \(x_0\) and \(x_m\) are adjacent to the centers of at least one \(K_{i,s}\), where \(s > 0\), and each \(x_i\), \(1 \leq i \leq m-1\), is at most adjacent to the centers of some \(K_{1,s}\), where \(s \geq 0\). This unique path \(H\) is called the central path of the lobster. We call \(K_{1,s}\) an even branch if \(s\) is nonzero even, an odd branch if \(s\) is odd, and a pendant branch if \(s = 0\). In this paper, we give graceful labelings to some new classes of lobsters with diameter at least five. In these lobsters, the degree of each vertex \(x_i\), \(0 \leq i \leq m-1\), is even and the degree of \(x_m\) may be odd or even, and we have one of the following features:

1. For some \(t_1, t_2, t_3\), \(0 \leq t_1 < t_2 < t_3 \leq m\), each \(x_i\), \(0 \leq i \leq t_1\), is attached to two types (odd and pendant), or all three types, of branches; each \(z_i\), \(t_1 + 1 \leq i \leq t_2\), is attached to all three types of branches; each \(x_i\), \(t_2 + 1 \leq i \leq t_3\), is attached to two types of branches; and if \(t_3 < m\) then each \(z_i\), \(t_3 + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.
2. For some \(t_1, t_2\), \(0 < t_1 < t_2 < m\), each \(x_i\), \(0 \leq i \leq t_1\), is attached to two types (odd and pendant), or all three types, of branches; each \(x_i\), \(t_1 + 1 \leq i \leq t_2\), is attached to two, or all three types of branches; and if \(t_2 < m\) then each \(x_i\), \(t_2 + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.
3. For some \(t\), \(0 \leq t \leq m\), each \(x_i\), \(0 \leq i \leq t\), is attached to all three types of branches; and if \(t < m\) then each \(x_i\), \(t + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.

In this paper, an algorithm for constructing self-centered graphs from trees and two more algorithms for constructing self-centered graphs from a given connected graph \(G\), by adding edges are discussed. Motivated by this, a new graph theoretic parameter \(sc_r(G)\), the minimum number of edges added to form a self-centered graph from \(G\) is defined. Bounds for this parameter are obtained and exact values of this parameter for several classes of graphs are also obtained.

A \((k;g)\)-graph is a \(k\)-regular graph with girth \(g\). A \((k;g)\)-cage is a \((k;g)\)-graph with the least number of vertices. In this note, we show that a \((k;g)\)-cage has an \(r\)-factor of girth at least \(g\) containing or avoiding a given edge for all \(r\), \(1 \leq r \leq k-1\).

This paper deals with the problem of constructing Hamiltonian paths of optimal weights in Halin graphs. There are three versions of the Hamiltonian path: none or one or two of end-vertices are specified. We present \(O(|V|)\) algorithms for all the versions of the problem.