Many results about outer-embeddings (graphs having all their vertices in the same face) have been obtained recently in topological graph theory in recent times. In this paper, we deal with some difficulties appearing in the study of such embeddings. Particularly, we propose several problems concerning outer-embeddings in pseudosurfaces and we prove that two of them are NP-complete.

We also describe some properties about lists of forbidden minors for outer-embeddings in certain kinds of pseudosurfaces.

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.