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.