Let \(G = (V, E)\) be a graph and \(A\) a non-trivial Abelian group, and let \(\mathcal{F}(G, A)\) denote the set of all functions \(f: E(G) \to A\). Denote by \(D\) an orientation of \(E(G)\). Then \(G\) is \(A\)-colorable if and only if for every \(f \in \mathcal{F}(G, A)\) there exists an \(A\)-coloring \(c: V(G) \to A\) such that for every \(e = (x,y) \in E(G)\) (assumed to be directed from \(x\) to \(y\)), \(c(x) – c(y) \neq f(e)\). If \(G\) is a graph, we define its group chromatic number \(\chi_1(G)\) to be the minimum number \(m\) for which \(G\) is \(A\)-colorable for any Abelian group \(A\) of order \(\geq m\) under the orientation \(D\). In this paper, we investigated the properties of the group chromatic number, proved the Brooks Type theorem for \(\chi_1(G)\), and characterized all bipartite graphs with group chromatic number at most \(3\), among other things.

A signed graph is an unoriented graph with a given partition \(E = E^+ \bigcup E^-\) of its edge-set. We define the arc signed graph \({A}(G)\) of an oriented graph \(G\) (G has no multiple arcs, opposite arcs, and loops). The arc signed graphs are similar to the line graphs. We prove both a Krausz-type characterization and a forbidden induced subgraph characterization (like the theorem of Beineke and Robertson on line graphs). Unlike line graphs, there are infinitely many minimal forbidden induced subgraphs for the arc signed graphs. Nevertheless, the arc signed graphs are polynomially recognizable. Also, we obtain a result similar to Whitney’s theorem on line graphs.

For a vertex \(v\) in a graph \(G\), we denote by \(N^2(v)\) the set \((N_1(N_1(v))\setminus \{v\})\cup N_1(v)=\{x\in V(G): 1 \leq d(x,v) \leq 2\}\), where \(d(x,v)\) denotes the distance between \(x\) and \(v\). A vertex \(v\) is \(N^2\)-locally connected if the subgraph induced by \(N^2(v)\) is connected. A graph \(G\) is called \(N^2\)-locally connected if every vertex of \(G\) is \(N^2\)-connected. A well-known result by Oberly and Sumner is that every connected locally connected claw-free graph on at least three vertices is Hamiltonian. This result was improved by Ryjacek using the concept of second-type neighborhood. In this paper, using the concept of \(N^2\)-locally connectedness, we show that every connected \(N^2\)-locally connected claw-free graph \(G\) without vertices of degree \(1\), which does not contain an induced subgraph \(H\) isomorphic to one of \(G_1, G_2, G_3\), or \(G_4\), is Hamiltonian, hereby generalizing the result of Oberly and Sumner (J. Graph Theory, \(3 (1979) 351-356\))and the result of \(Ryjacek\)( J. Graph Theory, \(14 (1990)\) 321-381)

On the gracefulness of graph \(C_m\bigcup P_n\), Frucht and Salinas that proved \(C_m\bigcup P_n\) is graceful and conjectured: \(C_m\bigcup P_n\) is graceful if and only if \(m+n=7\). In this paper, we prove graph \(C_m\bigcup P_n\) is graceful, for \(m=4k, n=k+2, k+3, 2k+1,\ldots, 2k+5;\) \(m=4k+1, n=2k, 3k+1, 4k+1;\) \(m=4k+2 n=3k, 3k+1,
4k+1; m=4k+3, n=2k+1, 3k, 4k\).

Let \(\nu(\mathbb{Z}^m)\) be the minimal number of colors enough to color the \(m\)-dimensional integer grid \(\mathbb{Z}^m\) so that there would be no infinite monochromatic symmetric subsets. Banakh and Protasov [3] compute \(\nu(\mathbb{Z}^m) = m+1\). For the one-dimensional case this just means that one can color positive integers in red, while negative integers in blue, thereby avoiding an infinite monochromatic symmetric subset by a trivial reason. This motivates the question what changes if we allow only colorings unlimited in both directions (in “all” directions for \(m > 1\)). In this paper we show that then \(\nu(\mathbb{Z})\) increases by \(1\), whereas for higher dimensions the values \(\nu(\mathbb{Z}^m)\) remain unaffected.
Furthermore we examine the density properties of a set \(A \subseteq \mathbb{Z}^m\) that ensure the existence of infinite symmetric subsets or arbitrarily large finite symmetric subsets in \(A\). In the case that \(A\) is a sequence with small gaps, we prove a multi-dimensional analogue of the Szemerédi theorem, with symmetric subsets in place of arithmetic progressions. A similar two-dimensional statement is known for collinear subsets (Pomerance [10]), whereas for two-dimensional arithmetic progressions even the corresponding version of van der Waerden’s theorem is known to be false.

The eccentricity of a vertex \(v\) in a connected graph \(G\) is the distance between \(v\) and a vertex farthest from \(v\). For a vertex \(v\), we define the edge-added eccentricity of \(v\) as the minimum eccentricity of \(v\) in all graphs \(G+e\), taken over all edges \(e\) in the complement of \(G\). A graph is said to be edge-added stable (or just stable) if the eccentricity and the edge-added eccentricity are the same for all vertices in the graph. This paper describes properties of edge-added eccentricities and edge-added stable graphs.

In this paper, we find explicit formulas or generating functions for the cardinalities of the sets \(S_n(T,\tau)\) of all permutations in \(S_n\) that avoid a pattern \(\tau \in S_k\) and a set \(T, |T| \geq 2,\) of patterns from \(S_3\). The main body of the paper is divided into three sections corresponding to the cases \(|T| = 2, 3\) and \(|T| \geq 4\). As an example, in the fifth section, we obtain the complete classification of all cardinalities of the sets \(S_n(T,\tau)\) for \(k = 4\).

The concept of weakly associative lattices (i.e. relational systems with a reflexive and antisymmetric relation \(\leq\), in which for each pair of elements there exist a least upper and a greatest lower bound) was introduced in [3] and [5]. In [4] WU-systems are defined, i.e. weakly associative lattices with the unique bound property, and their equivalence with projective planes is described. In this paper we introduce WU\(_{\lambda}\)-systems, and discuss their relation to symmetric \(2\)-\((v,k,\lambda)\) designs equipped with a special “loop-free” mapping.

It is shown in this paper that every \(2\)-connected claw-free graph containing a \(k\)-factor has a connected \([k,k+1]\)-factor, where \(k \geq 2\).

Let \(G\) be a graph of order \(n\), and let \(n = \sum_{i=1}^{k}a^i\) be a partition of \(n\) with \(a_i \geq 2\). Let \(v_1, \ldots, v_k\) be given distinct vertices of \(G\). Suppose that the minimum degree of \(G\) is at least \(3k\). In this paper, we prove that there exists a decomposition of the vertex set \(V(G) = \bigcup_{i=1}^k A_i\) such that \(|A_i| = a_i\), \(v_i \in A_i\), and the subgraph induced by \(A_i\) contains no isolated vertices for all \(i, 1 \leq i \leq k\).

Let \(G\) be a graph of order \(n \geq 4k\) and let \(S\) be the graph obtained from \(K_4\) by removing two edges which have a common vertex. In this paper, we prove the following theorem:
A graph \(G\) of order \(n \geq 4k\) with \(\sigma_2(G) \geq n+k\) has \(k\) vertex-disjoint \(S\).This theorem implies that a graph \(G\) of order \(n = 4k\) with \(\sigma_2(G) \geq 5k\) has an \(S\)-factor.

The reconstruction number \(rn(G)\) of graph \(G\) is the minimum number of vertex-deleted subgraphs of \(G\) required in order to identify \(G\) up to isomorphism. Myrvold and Molina have shown that if \(G\) is disconnected and not all components are isomorphic then \(rn(G) = 3\), whereas, if all components are isomorphic and have \(c\) vertices each, then \(rn(G)\) can be as large as \(c + 2\). In this paper we propose and initiate the study of the gap between \(rn(G) = 3\) and \(rn(G) = c + 2\). Myrvold showed that if \(G\) consists of \(p\) copies of \(K_c\), then\(rn(G) = c + 2\). We show that, in fact, this is the only class of disconnected graphs with this value of \(rn(G)\). We also show that if \(rn(G) \geq c + 1\) (where \(c\) is still the number of vertices in any component), then, again, \(G\) can only be copies of \(K_c\). It then follows that there exist no disconnected graphs \(G\) with \(c\) vertices in each component and \(rn(G) = c + 1\). This poses the problem of obtaining for a given \(c\), the largest value of \(t = t(c)\) such that there exists a disconnected graph with all components of order \(c\), isomorphic and not equal to \(K_c\), and is such that \(rn(G) = t\).

We take a special \(1\)-factorization of \(K_{n,n}\), and investigate the subgraphs suborthogonal to the \(1\)-factorization. Some interesting results are obtained, including an identity involving \(n^n\) and \(n!\) and a property of permutations.

An extended Mendelsohn triple system of order \(v\) (EMTS(\(v\))) is a collection of cyclically ordered triples of the type \([x,y,z], [x,x,y]\), or \([x,x,x]\) chosen from a \(v\)-set, such that each ordered pair (not necessarily distinct) belongs to exactly one triple. If such a design with parameters \(v\) and \(a\) exist, then they will have \(b_{v,a}\) blocks, where \(b_{v,a} = (v^2 + 2a)/3\). In this paper, we show that there are two (not necessarily distinct) EMTS(\(v\))’s with common triples in the following sets:

\(\{0,1,2,\ldots,b_v-4,b_v-2,b_v\}\), if \(v \neq 6\); and

\(\{0,1,2,\ldots,b_v-4,b_v-2\}\), if \(v = 6\),

where \(b_v\) is \(b_{v,v-1}\) if \(v \equiv 2 \pmod{3}\); \(b_{v,v}\) if \(v \not\equiv 2 \pmod{3}\).

Dudeney’s round table problem was proposed about one hundred years ago. It is already solved when the number of people is even, but it is still unsettled except for only a few cases when the number of people is odd.

In this paper, a solution of Dudeney’s round table problem is given when \(n = p+2\), where \(p\) is an odd prime number such that \(2\) is the square of a primitive root of \(\mathrm{GF}(p)\), and \(p \equiv 3 \pmod{4}\).

The number \(g^{(4)}_{2}\) is the minimal number of blocks that contain all pairs from a set of \(8\) elements exactly twice under the restriction that the longest block has size \(4\) (this longest block need not be unique). Thus the blocks have lengths \(2, 3\), and \(4\). We show that there are three solutions to this problem.

The \(n \times n\) primitive nearly reducible Boolean matrices whose \(k\)-exponents (\(1 \leq k \leq n\)) achieve the maximum value are characterized.

A graph is said to be \(k\)-covered if for each edge \(xy\), \(deg(x) = k\) or \(deg(y) = k\). In this paper, we characterize the \(3\)-covered quadrangulations of closed surfaces.

A graceful graph with \(n\) edges and \(n+1\) vertices is called a vertex-saturated graph. Each graceful graph corresponds to a vertex-saturated graph. Four classes of graceful graphs associated with vertex-saturated graphs are presented. Three of which generalize the results of [1], [2] and [5].

We correct an earlier theorem and reprove its consequences regarding \(c\)-BRDs with \(v \equiv 5, 8 \pmod{12}\). The original conclusions remain valid.

The type of a vertex \(v\) in a \(p\)-page book-embedding is the \(p \times 2\) matrix of nonnegative integers

\[{r}(v) =
\left(
\begin{array}{ccccc}
l_{v,1} & r_{v,1} \\
. & . \\
. & . \\
. & . \\
l_{v,p} & r_{v,p} \\
\end{array}
\right),\]

where \(l_{v,i}\) (respectively, \(r_{v,i}\)) is the number of edges incident to \(v\) that connect on page \(i\) to vertices lying to the left (respectively, to the right) of \(v\). The type number of a graph \(G\), \(T(G)\), is the minimum number of different types among all the book-embeddings of \(G\). In this paper, we disprove the conjecture by J. Buss et al. which says for \(n \geq 4\), \(T(L_n)\) is not less than \(5\) and prove that \(T(L_n) = 4\) for \(n \geq 3\).

Let \(T\) be a chemical tree, i.e. a tree with all vertices of degree less than or equal to \(4\). We find relations for the \(0\)-connectivity and \(1\)-connectivity indices \({}^0\chi(T)\) and \({}^1\chi(T)\), respectively, in terms of the vertices and edges of \(T\). A comparison of these relations with the coefficients of the characteristic polynomial of \(T\) associated to its adjacency matrix is established.

Given a regular action of a finite group \(G\) on a set \(V\), we consider the problem of the existence of an incidence structure \(\mathcal{I} = (V, \mathcal{B})\) on the set \(V\) whose full automorphism group \(Aut(\mathcal{I})\) is the group \(G\) in its regular action. Using results on graphical and digraphical regular representations \(([2,7], [1])\), we show the existence of such an incidence structure for all but four small finite groups.

For a finite field \({F} = {F}(q)\), where \(q = p^n\) is a prime power, we will introduce the notion of equivalence of subsets of \(F\) which stems out of the equivalence of cyclic difference sets, and give the formulae for the number of equivalence classes of \(k\)-subsets of \(F\) as well as for the number of equivalence classes of subsets of \(F\) by using Pólya’s theorem of counting.

We present an algorithmic construction of anti-Pasch Steiner triple systems for orders congruent to \(9\) mod \(12\). This is a Bose-type method derived from a particular type of \(3\)-triangulations generated from non-sum-one-difference-zero sequences (\(NS1D0\) sequences). We introduce \(NS1D0\) sequences and describe their basic properties; in particular, we develop an equivalence between the problem of finding \(NS1D0\) sequences and a variant of the \(n\)-queens problem. This equivalence, and an algebraic characterization of the \(NS1D0\) sequences that produce anti-Pasch Steiner triple systems, form the basis of our algorithm.

For vertices \(u\) and \(v\) in a nontrivial connected graph \(G\), the closed interval \([u,v]\) consists of \(u\), \(v\), and all vertices lying in some \(u-v\) geodesic of \(G\). For \(S \subseteq V(G)\), the set \(I[S]\) is the union of all sets \(I[u,v]\) for \(u,v \in S\). A set \(S\) of vertices of a graph \(G\) is a geodetic set in \(G\) if \(I[S] = V(G)\). The minimum cardinality of a geodetic set in \(G\) is its geodetic number \(g(G)\). A subset \(T\) of a minimum geodetic set \(S\) in a graph \(G\) is a forcing subset for \(S\) if \(S\) is the unique minimum geodetic set containing \(T\). The forcing geodetic number \(f(S)\) of \(S\) in \(G\) is the minimum cardinality of a forcing subset for \(S\), and the upper forcing geodetic number \(f^+(G)\) of the graph \(G\) is the maximum forcing geodetic number among all minimum geodetic sets of \(G\). Thus \(0 \leq f^+(G) \leq g(G)\) for every graph \(G\). The upper forcing geodetic numbers of several classes of graphs are determined. It is shown that for every pair \(a,b\) of integers with \(0 \leq a \leq b\) and \(b \geq 1\), there exists a connected graph \(G\) with \(f^+(G) = a\) and \(g(G) = b\) if and only if \((a, b) \notin \{(1, 1), (2,2)\}\).