Let \(G\) be a graph with integral edge weights. A function \(d: V(G) \to \mathbb{Z}_p\) is called a nowhere \(0 \mod p\) domination function if each \(v \in V\) satisfies \((\sum_{u \in N(v)} w(u,v)d(u))\neq 0 \mod p\), where \(w(u,v)\) denotes the weight of the edge \((u,v)\) and \(N(v)\) is the neighborhood of \(v\). The subset of vertices with \(d(v) \neq 0\) is called a nowhere \(0 \mod p\) dominating set. It is known that every graph has a nowhere \(0 \mod 2\) dominating set. It is known to be false for all other primes \(p\). The problem is open for all odd \(p\) in case all weights are one.

In this paper, we prove that every unicyclic graph (a graph containing at most one cycle) has a nowhere \(0 \mod p\) dominating set for all \(p > 1\). In fact, for trees and cycles with any integral edge weights, or for any other unicyclic graph with no edge weight of \((-1) \mod p\), there is a nowhere \(0 \mod p\) domination function \(d\) taking only \(0-1\) values. This is the first nontrivial infinite family of graphs for which this property is established. We also determine the minimal graphs for which there does not exist a \(0 \mod p\) dominating set for all \(p > 1\) in both the general case and the \(0-1\) case.

We apply the technique of patchwork embeddings to find orientable genus embeddings of the Cartesian product of a complete regular tripartite graph with an even cycle. In particular, the orientable genus of \(K_{m,m,m} \times C_{2n}\) is determined for \(m \geq 1\) and for all \(n \geq 3\) and \(n = 1 \). For \(n = 2\) both lower and upper bounds are given.

We see that the resulting embeddings may have a mixture of triangular and quadrilateral faces, in contrast to previous applications of the patchwork method.

The redundancy \(R(G)\) of a graph \(G\) is the minimum, over all dominating sets \(S\), of \(\sum_{v \in S} 1 + d(v)\), where \(d(v)\) is the degree of vertex \(v\). We establish a sharp upper bound on the redundancy of trees and characterize all trees that achieve the bound.

We first prove that for any fixed \(k\), a cubic graph with few short cycles contains a \(K_{k}\)-minor. This is a direct generalization of a result on girth by Thomassen. We then use this theorem to show that for any fixed \(k\), a random cubic graph contains a \(K_{k}\)-minor asymptotically almost surely.

Partial parallelisrms Uhat admit a collineation group that fixes one spread \(\Sigma\), fixes a line of it and acts sharply two-transitive on the remaining lines of \(\Sigma\) are completely classified.

Recently, Babson and Steingrimsson (see \([BS]\)) introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation.

Following \([BCS]\), let \(e_k,m\) (respectively, \(f_k\pi\)) be the number of occurrences of the generalized pattern \(12-3-\ldots-k\) (respectively, \(21-3-\ldots-k\)) in a permutation \(\pi\). In the present note, we study the distribution of the statistics \(e_k,f_k\) and \(f_k\pi\) in a permutation avoiding the classical pattern \(1-3-2\).

We also present some applications of our results, which relate the enumeration of permutations avoiding the classical pattern \(1-3-2\) according to the statistics \(e_k\) and \(f_k\) to Narayana numbers and Catalan numbers.

We show that a negation of tautology corresponds to a family of graphs without nowhere-zero group- and integer-valued flows.

We show that in any graph \(G\) on \(n\) vertices with \(d(x) + d(y) \geq n\) for any two nonadjacent vertices \(x\) and \(y\), we can fix the order of \(k\) vertices on a given cycle and find a Hamiltonian cycle encountering these vertices in the same order, as long as \(k < n/12\) and \(G\) is \([(k+1)/2]\)-connected. Further, we show that every \([3k/2]\)-connected graph on \(n\) vertices with \(d(x) + d(y) \geq n\) for any two nonadjacent vertices \(x\) and \(y\) is \(k\)-ordered Hamiltonian, i.e., for every ordered set of \(k\) vertices, we can find a Hamiltonian cycle encountering these vertices in the given order. Both connectivity bounds are best possible.

We establish that for any \(m \in \mathbb{N}\) and any \(K_m\)-free graph \(G\) on \(\mathbb{N}\), there exist large additive and multiplicative structures that are independent with respect to \(G\). In particular, there exists for each \(l \in \mathbb{N}\) an arithmetic progression \(A_l\) of length \(l\) with increment chosen from the finite sums of a prespecified sequence \(\langle t_{l,n}\rangle _{n=1}^{\infty}\), such that \(\bigcup_{i=1 }^\infty A_l\) is an independent set. Moreover, if \(F\) and \(H\) are disjoint finite subsets of \(\mathbb{N}\), and for each \(t \in F \cup H\), \(a_t \in A_l\), then \(\{\Sigma_{t \in F}a_t\Sigma_{t \in H} a_t\}\) is not an edge of \(G\). If \(G\) is \(K_{m,m}\)-free, one may drop the disjointness assumption on the sets \(F\) and \(H\). Analogous results are valid for geometric progressions.

A connected graph \(G(V, E)\) is said to be \((a, d)\)-antimagic if there exist positive integers \(a\) and \(d\) and a bijection \(f: E \to \{1, 2, \ldots, |E|\}\) such that the induced mapping \(g_f: V \to \mathbb{N}\) defined by \(g_f(v) = \sum\{f(u,v) | (u, v) \in E(G)\}\) is injective and \(g_f(V) = \{a, a+d, a+2d, \ldots, a+(|V|-1)d\}\). In this paper, we mainly investigate \((a, d)\)-antimagic labeling of some special trees, complete bipartite graphs \(K_{m,n}\), and categorize \((a, d)\)-antimagic unicyclic graphs.

A graph \(G = (V, E)\) is said to be an \(integral \;sum \;graph\) ( respectively, \(sum \;graph\)) if there is a labeling \(f\) of its vertices with distinct integers ( respectively, positive integers) , so that for any two vertices \(u\) and \(v\), \(uv\) is an edge of \(G\) if and only if \(f(u) + f(v) = f(w)\) for some other vertex \(w\). For a given graph \(G\), the \(integral\; sum\; number\) \(\zeta = \zeta(G)\) (respectively, \(sum\; number\) \(\sigma = \sigma(G)\) ) is defined to be the smallest number of isolated vertices which when added to \(G\) result in an integral sum graph (respectively, sum graph). In a graph \(G\), a vertex \(v \in V(G)\) is said to a \(hanging\; vertex\) if the degree of it \(d(v) = 1\). A path \(P \subseteq G\), \(P = x_ox_1x_2\ldots x_t\), is said to be a \(hanging\; path\) if its two end vertices are respectively a hanging vertex \(x_o\) and a vertex \(x_t\) whose degree \(d(x_t) \neq 2\) where \(d(x_j) = 2 (j = 1,2,\ldots,t – 1)\) for every other vertex of \(P\). A hanging path \(P\) is said to be a tail of \(G\), denoted by \(t(G)\), if its length \(|t(G)|\) is a maximum among all hanging paths of \(G\). In this paper, we prove \(\zeta(T_3) = 0\), where \(T_3\) is any tree with \(|t(T_3)| \geq 3\). The result improves a previous result for integral sum trees from identification of Chen\((1998)\).

Let \(H = K_{k_1,k_2,\ldots,k_t}\) be a complete multipartite graph having \(t \geq 3\) parts. Extending the well-known result that a simple graph \(G\) or its complement, \({G}\), is connected, it is proved that in any coloring of the edges of \(H\) with two colors, blue and red, at least one of the subgraphs induced by the blue edges or by the red edges, is connected.

Given a collection of points in the plane, a circle is drawn around each point with radius equal to the smallest distance from that point to any other in the collection. The sphere-of-influence graph is the intersection graph of the open balls given by these circles. Any graph isomorphic to such a graph is a SIG realizable in a plane. Similarly, one can define a SIG realizable on a sphere by selecting a collection of points on a sphere. We show that \(K_9\) is realizable as a SIG on a sphere and that the family of graphs realizable as SIGs on a sphere is at least as large as the family of SIGs in the plane.

In this paper, we construct many Hadamard matrices of order \(44\) and we use a new efficient algorithm to investigate the lower bound of inequivalent Hadamard matrices of order \(44\). Using four \((1, -1)\)-circulant matrices of order \(11\) in the Goethals-Seidel array, we obtain many new Hadamard matrices of order \(44\) and we show that there are at least \(6018\) inequivalent Hadamard matrices for this order. Moreover, we use a known method to investigate the existence of double even self-dual codes \([88, 44, d]\) over \(\text{GF}(2)\) constructed from these Hadamard matrices.

Given positive integers \(m, k,\) and \(t\). Let \(D_{m,[k,k+i]} = \{1,2,\ldots,m\} – \{k,k+1,\ldots,k+i\}\). The distance graph \(G(\mathbb{Z}, D_{m,[k,k+i]})\) has vertex set all integers \(\mathbb{Z}\) and edges connecting \(j\) and \(j’\) whenever \(|j-j’| \in D_{m,[k,k+i]}\). The fractional chromatic number, the chromatic number, and the circular chromatic number of \(G(\mathbb{Z}, D_{m,k,i})\) are denoted by \(\chi_f(\mathbb{Z}, D_{m[k,k+i]}), \chi(\mathbb{Z}, D_{m,[k,k+i]}),\) and \(\chi_c(\mathbb{Z}, D_{m,[k,k+i]})\), respectively. For \(i=0\), we simply denote \(D_{m,[k,k+0]}\) by \(D_{m,k}\). \(X(\mathbb{Z}, D_{m,k})\) was studied by Eggleton, Erdős and Skilton [5], Kemnitz and Kolberg [8], and Liu [9], and was completely solved by Chang, Liu and Zhu [1] who also determined \(\chi_c(\mathbb{Z}, D_{m,k})\) for any \(m\) and \(k\). The value of \(\chi_c(\mathbb{Z}, D_{m,k})\) was studied by Chang, Huang and Zhu [2] who finally determined \(\chi_c(\mathbb{Z}, D_{m,k})\) for any \(m\) and \(k\). This paper extends the study of \(G(\mathbb{Z}, D_{m,[k,k+i]})\) to values \(i\) with \(1 \leq i \leq k-1\). We completely determine \(\chi_f(\mathbb{Z}, D_{m,[k,k+i]})\) and \(\chi(\mathbb{Z}, D_{m,k,i})\) for any \(m\) and \(k\) with \(1 \leq i \leq k-1\). However, for \(\chi_c(\mathbb{Z}, D_{m,[k,k+i]})\), only some special cases are determined.

We introduce graphs \(G\) with at least one maximum independent set of vertices \(I\), such that \(\forall v \in V(G) \setminus I\), the number of vertices in \(N_G(v) \cap I\) is constant. When this number of vertices is equal to \(\lambda\), we say that \(I\) has the \(\lambda\)-property and that \(G\) is \(\lambda\)-regular-stable. Furthermore, we extend the study of this property to the well-covered graphs (that is, graphs where all maximal independent sets of vertices have the same cardinality). In this study, we consider well-covered graphs for which all maximal independent sets of vertices have the \(\lambda\)-property, herein called well-covered \(\lambda\)-regular-stable graphs.

Isometric subgraphs of hypercubes are known as partial cubes. Edge-critical partial cubes are introduced as the partial cubes \(G\) for which \(G – e\) is not a partial cube for any edge \(e\) of \(G\). An expansion theorem is proved by means of which one can generate many edge-critical partial cubes. Edge-critical partial cubes are characterized among the Cartesian product graphs. We also show that the \(3\)-cube and the subdivision graph of \(K_4\) are the only edge-critical partial cubes on at most \(10\) vertices.

This paper discusses the enumeration of rooted labelled spanning forests of the complete bipartite graph \(K_{m,n}\).

A set of edges \(D\) in a graph \(G\) is a dominating set of edges if every edge not in \(D\) is adjacent to at least one edge in \(D\). The minimum cardinality of an edge dominating set of \(G\) is the edge domination number of \(G\), denoted by \(D_E(G)\). In this paper, we investigate the edge domination number for the cartesian product of an \(n\)-colorable graph \(G\) and the complete graph \(K_n\).

For graph \(G\) with non-empty edge set, a \((j,k)\)-edge labeling of \(G\) is an integer labeling of the edges such that adjacent edges receive labels that differ by at least \(j\), and edges which are distance two apart receive labels that differ by at least \(k\). The \(\lambda’_{j,k}\)-number of \(G\) is the minimum span over the \((j,k)\)-edge labelings of \(G\). By establishing the equivalence of the edge labelings of \(G\) to particular vertex labelings of \(G\) and the line graph of \(G\), we explore the properties of \(\chi_{j,k}(G)\). In particular, we obtain bounds on \(\lambda’_{j,k}(G)\), and prove that the \(\Delta^2\) conjecture of Griggs and Yeh is true for graph \(H\) if \(H\) is the line graph of some graph \(G\). We investigate the \(\lambda’_{1,1}\)-numbers and \(\lambda_{2,1}\)-numbers of common classes of graphs, including complete graphs, trees, \(n\)-cubes, and joins.

The \(n \times n\) Lah matrix \(L_n\) is defined by \((L_n)_{ij} = l(i, j)\), where \({l}(i, j)\) is the unsigned Lah number. In this paper, we investigate the algebraic properties of \(L_n\), and many important relations between \({L}_n\) and Pascal matrix and Stirling matrix, respectively. In addition, we obtain its exponential expansion and Pascal matrix factorization. Furthermore, we introduce a simple method to find and prove combinatorial identities.

Let \(K_n\) be the complete graph on \(n\) vertices. In this paper, we find the necessary and sufficient conditions for the existence of an \((m_1, m_2, \ldots, m_r)\)-cycle system of \(K_n\), where \(m_i\) (\(1 \leq i \leq r\)) are positive even integers, and \(\sum_{i=1}^{r}m_i = 2^k\) for \(k \geq 2\). In particular, if \(r = 1\) then there exists a cyclic \(2^k\)-cycle system of \(K_n\) if and only if \(2^k\) divides \(|E(K_n)|\) and \(n\) is odd.

In 1948, de Bruijn and Erdős proved that every finite linear space on \(v\) points and with \(6\) lines fulfils the inequality \(b \geq v\), and the equality holds if the linear space is a (possibly degenerate) projective plane. This result led to the problem of classifying finite linear spaces on \(v\) points and with \(b = v + s\) lines, \(s \geq 1\). This paper contains the classification of finite linear spaces on \(v\) points and with \(b = v + 4\) lines.

For a vertex \(v\) of a connected graph \(G\) and a subset \(S\) of \(V(G)\), the distance between \(v\) and \(S\) is \(d(v,S) = \min\{d(v,z)|z \in S\}\). For an ordered \(k\)-partition \(\Pi = \{S_1,S_2,\ldots,S_k\}\) of \(V(G)\), the code of \(v\) with respect to \(\Pi\) is the \(k\)-vector \(c_\Pi(v) = (d(v, S_1), d(v, S_2), \ldots, d(v,S_k))\). The \(k\)-partition \(\Pi\) is a resolving partition if the \(k\)-vectors \(c_\Pi(v), v \in V(G)\), are distinct. The minimum \(k\) for which there is a resolving \(k\)-partition of \(V(G)\) is the partition dimension \(pd(G)\) of \(G\). A resolving partition \(\Pi = \{S_1,S_2,\ldots,S_k\}\) of \(V(G)\) is a resolving-coloring if each \(S_i\) (\(1 \leq i \leq k\)) is independent and the resolving-chromatic number \(\chi_r(G)\) is the minimum number of colors in a resolving-coloring of \(G\). A resolving partition \(\Pi = \{S_1,S_2,\ldots,S_k\}\) is acyclic if each subgraph \((S_i)\) induced by \(S_i\) (\(1 \leq i \leq k\)) is acyclic in \(G\). The minimum \(k\) for which there is a resolving acyclic \(k\)-partition of \(V(G)\) is the resolving acyclic number \(\alpha_r(G)\) of \(G\). Thus \(2 \leq pd(G) < \alpha_r(G) \leq \chi_r(G) \leq n\) for every connected graph \(G\) of order \(n \geq 2\). We present bounds for the resolving acyclic number of a connected graph in terms of its arboricity, partition dimension, resolving-chromatic number, diameter, girth, and other parameters. Connected graphs of order \(n \geq 3\) having resolving acyclic number \(2, n,\) or \(n-1\) are characterized.

Let \(p\) and \(q\) be distinct primes with \(p > q\) and \(n\) a positive integer. In this paper, we consider the set of possible cross numbers for the cyclic groups \(\mathbb{Z}_{2p^n}\) and \(\mathbb{Z}_{pq}\). We completely determine this set for \(\mathbb{Z}_{2p^n}\) and also \(\mathbb{Z}_{pq}\) for \(q = 3, q = 5\) and the case where \(p\) is sufficiently larger than \(g\). We view the latter result in terms of an upper bound for this set developed in a paper of Geroldinger and Schneider [8] and show precisely when this upper bound is an equality.

It is known that triangles with vertices in the integral lattice \(\mathbb{Z}^2\) and exactly one interior lattice point can have \(3, 4, 6, 8\), and \(9\) lattice points on their boundaries. No such triangles with \(5\), nor \(7\), nor \(n \geq 10\) boundary lattice points exist. The purpose of this note is to study an analogous property for Hex-triangles, that is, triangles with vertices in the set \(H\) of corners of a tiling of \(\mathbb{R}^2\) by regular hexagons of unit edge. We show that any Hex-triangle with exactly one interior \(H\)-point can have \(3, 4, 5, 6, 7, 8,\) or \(10\), \(H\)-points on its boundary and cannot have \(9\) nor \(n \geq 11\) such points.

The problem of classification of Hadamard matrices becomes an NP-hard problem as the order of the Hadamard matrices increases. In this paper, we use a new criterion which inspired us to develop an efficient algorithm to investigate the lower bound of inequivalent Hadamard matrices of order \(36\). Using four \((1,-1)\) circulant matrices of order \(9\) in the Goethals-Seidel array, we obtain many new Hadamard matrices of order \(36\) and we show that there are at least \(1036\) inequivalent Hadamard matrices for this order.

We prove the gracefulness of two classes of graphs.

Let \(G\) be a graph with \(q\) edges. \(G\) is numbered if each vertex \(v\) is assigned a non-negative integer \(\phi(v)\) and each edge \(uv\) is assigned the value \(|\phi(u) – \phi(v)|\). The numbering is called graceful if, further, the vertices are labelled with distinct integers from \(\{0, 1, 2, \ldots, q\}\) and the edges with integers from \(1\) to \(q\). A graph which admits a graceful numbering is said to be graceful. For the literature on graceful graphs see [1, 2] and the relevant references given in them.

Let \(G\) be a graph and let \(c\) be a coloring of its edges. If the sequence of colors along a walk of \(G\) is of the form \(a_1, \ldots, a_n, a_1, \ldots, a_n\), the walk is called a square walk. We say that the coloring \(c\) is square-free if any open walk is not a square and call the minimum number of colors needed so that \(G\) has a square-free coloring a walk Thue number and denote it by \(\pi_w(G)\). This concept is a variation of the Thue number introduced by Alon, Grytczuk, Hatuzczak, and Riordan in [2].

Using the walk Thue number, several results of [1] are extended. The Thue number of some complete graphs is extended to Hamming graphs. This result (for the case of hypercubes) is used to show that if a graph \(G\) on \(n\) vertices and \(m\) edges is the subdivision graph of some graph, then \(\pi_w(G) \leq n – \frac{m}{2}\). Graph products are also considered. An inequality for the Thue number of the Cartesian product of trees is extended to arbitrary graphs and upper bounds for the (walk) Thue number of the direct and the strong products are also given. Using the latter results, the (walk) Thue number of complete multipartite graphs is bounded, which in turn gives a bound for arbitrary graphs in general and for perfect graphs in particular.