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\).