A prime labeling of a simple finite graph \(G\) is a labeling of the vertices with distinct integers from \(\{1,2, \dots, |G|\}\) such that the labels of any two adjacent vertices are coprime. If \(G\) admits such a labeling, we call \(G\) a prime graph. If the set \(\{1,2, \dots, |G|\}\) is replaced by \(\{k,k+1, \dots, k+|G|-1\}\) in the previous definition, then we call it \(k\)-prime labeling, where \(k\) is a positive integer. Since some graph might be 2-prime labeling but not 3-prime labeling, to avoid ambiguity, we define uniform prime labeling for graphs. Focused on trees, using some very classical number theory results, we show that any star is uniform prime if and only if it has at most 16 vertices. We also prove any tree of order \(n\) with diameter \(n-1\), \(n-2\), \(n-3\), and \(n-4\) are uniform prime. Based on these results and several trees with diameter \(n-5\), we show that any tree with at most 8 vertices (There are 1+1+1+2+3+6+11+23=48 such non-isomorphic trees) are uniform prime. We also verified the uniform primality of several periodically constructed trees. We post some open questions and conjectures which should be essential and interesting by the end of Section 4. For example, we conjecture all the trees with order up to 16 are uniform prime and ask if there exists a tree other than star is not uniform prime.

Let \(G(V,E)\) be a finite simple graph. Denote by \(|V|\) and \(|E|\) the cardinality of the set \(V\) and \(E\), respectively. An \(\alpha\)-labeling \(f\) is an injective function \({f}:V\rightarrow \{0,1,2,…, |E|\}\) such that \(\{|f(u)-f(v)|:uv\in E\}=\{1,2,…,|E|\}\) and for a constant \(\lambda\), \(f(u)\le \lambda <f(v)\) for every \(uv\in E\). A graph that has an \(\alpha\)-labeling is called \(\alpha\)-graph. An open chain graph, or shortly a chain graph, is a graph with blocks \({B_1,B_2,…,B_n}\) such that for every \(i\), \(B_i\) and \(B_{i+1}\) have a common vertex, in such a way that the block-cut-vertex graph is a path. A chain graph having \({n}\) blocks \({B_1,B_2,…,B_n}\) is denoted by \([B_{1},B_{2},…,B_{n}]\). Let \({c_i}\) be the common vertex of \({B_i}\) and \({B_{i+1}}\), in \([{B_1,B_2,…,B_n}]\), \(1\le i \le n-1\). Consider a vertex of \({B_1}\), \({c_0 \ne c_1}\), and a vertex of \({B_n}\), \({c_n \ne c_{n-1}}\). Assume that \(B\) is another block graph and \(x\) and \(y\) are two different vertices in \(B\). The graph which is constructed by identifying \(c_0\) with \(x\) and \(c_n\) with \(y\) is called closed chain graph, and is denoted by \([{B_1,B_2,…,B_n,B}]_c\). By using pattern recognition and axiomatic deductive method we get results that some chain graphs with blocks of complete bipartite graphs are \(\alpha\)-labeling.

A cancellable fraction is a displayed numerator–denominator pair in which deleting the same decimal digit from the numerator and denominator leaves the represented rational number unchanged. We study vertical cancellations, where the deleted digits occur in the same decimal position in the numerator and denominator. Fix a nonzero digit \(h\). Let \(C_h(n)\) denote the number of marked vertical cancellations of the digit \(h\) among numerator–denominator pairs \((N,D)\), where \(N\) and \(D\) are both \(n\)-digit positive integers and \(D<N\). Here marked means that the cancelled position is part of the data. We prove that \[C_h(n)=O_h(n^2 10^{n-1}).\] Since the number of such displayed pairs \((N,D)\) is of order \(10^{2n}\), the proportion of vertically \(h\)-cancellable pairs is \(O_h(n^2/10^n)\). Thus vertical \(h\)-cancellability is exponentially rare. We also give an explicit family showing that \(C_h(n)\ge c_h10^n\) for all sufficiently large \(n\), and we include exact enumerations for small values of \(n\). Finally, we formulate a uniqueness conjecture asserting that almost every marked vertical cancellation belongs to a pair that is cancellable in exactly one vertical way.

A vertex set \(D\) in a finite undirected graph \(G\) is an efficient dominating set (e.d.s. for short) of \(G\) if every vertex of \(G\) is dominated by exactly one vertex of \(D\). The Efficient Domination (ED) problem asks for the existence of an e.d.s. in \(G\). The Weighted Efficient Dominating Set (WED for short) problem further asks for an e.d.s. of minimum/maximum weight in a given graph \(G\). The ED problem is known to be NP-complete, even for claw-free graphs, for \(P_7\)-free graphs, for chordal bipartite graphs, for planar bipartite graphs of maximum degree 3 and girth at least \(g\) for every fixed \(g\), and thus for \(C_4\)-free bipartite graphs. This manuscript reports a study on the WED problem for \(C_4\)-free bipartite graphs (in the context of a study for bipartite graphs) and shows that the WED problem can be solved in polynomial time for (\(S_{1,2,5},C_4\))-free bipartite graphs, for (\(P_{10},C_4\))-free bipartite graphs, and for some related graphs classes.

In this note, we give two simple bijections between compositions over groups and colorings of cycles. These bijections immediately imply the formulas for the number of \(m\)-compositions over a finite group.

Let \(G=(V(G),E(G))\) be a simple, finite and undirected graph of order \(p\) and size \(q\). For \(k\ge 1\), a bijection \(f: V(G)\cup E(G) \to \{k, k+1, k+2, \ldots, k+p+q-1\}\) such that \(f(uv)= |f(u) – f(v)|\) for every edge \(uv\in E(G)\) is said to be a \(k\)-super graceful labeling of \(G\). We say \(G\) is \(k\)-super graceful if it admits a \(k\)-super graceful labeling. In this paper, we study the \(k\)-super gracefulness of some complete multi-partite graphs.

Let \(G\) be a graph, or digraph, and let \(P=\{P_1,\dots,P_k\}\) be a partition of its vertex set. We solve the following problem: find the generating function, in the edge variables of \(G\), of the spanning trees of \(G\) each of whose restrictions to every part \(P_i\) is a spanning tree of the induced subgraph \(G[P_i]\); and, in the directed case with a fixed root \(v_i\in P_i\) for each \(i\), of the spanning arbors of \(G\) rooted at \(v_1\) each of whose restrictions to \(P_i\) is a spanning arbor of \(G[P_i]\) rooted at \(v_i\). We show that both generating functions factor as a product of the local generating functions on the parts \(G[P_i]\) (or \(P_i\), in the digraph case) with the generating function of spanning trees/arbors of a naturally associated contracted multigraph whose vertices are the parts of \(P\). This localizes the classical theorems of Kirchhoff and Tutte and yields an exact identity, and a family of lower bounds, for the number of spanning trees of \(G\) in terms of spanning-tree counts of smaller induced subgraphs.

Hartnell and Rall recently introduced the domatic number game. Alice and Bob color the vertices of a graph from a palette [\(k\)], and Alice wins if every color class is a dominating set at the end of the game. The largest winning palette size is denoted by \(\mathop{\mathrm{dom}}\nolimits_{g}(G)\) when Alice moves first and by \(\mathop{\mathrm{dom}}\nolimits’_{g}(G)\) when Bob moves first. Hartnell and Rall asked how these parameters behave under edge and vertex removal, and they also asked whether Bob can win with \(k\) colors while Alice wins with \(k+1\) colors. We give short answers. First, Alice-winning palettes are downward closed: if Alice can win with \(k+1\) colors, then she can win with \(k\) colors, in both versions of the game. Thus the proposed palette-size pathology never occurs. Second, if \(H\) is a spanning subgraph of \(G\), then
\[
\mathop{\mathrm{dom}}\nolimits_{g}(H)\le \mathop{\mathrm{dom}}\nolimits_{g}(G),\qquad \mathop{\mathrm{dom}}\nolimits’_{g}(H)\le \mathop{\mathrm{dom}}\nolimits’_{g}(G).
\]
Thus edge deletion can never increase either invariant, and the inequalities may be strict. Finally, vertex deletion is not monotone: it can increase or decrease either invariant. Deleting one vertex can even increase either invariant by an arbitrarily large amount.

For a graph \(G\) on \(n\) vertices, denote by \(a(G)\) the number of vertices in the largest induced forest in \(G\). The Albertson-Berman conjecture, which has been open since 1979, states that \(a(G) \geq \frac{n}{2}\) for every simple planar graph \(G\). We show that the version of this problem for multigraphs (allowing parallel edges) is easily reduced to the problem about the independence number of simple planar graphs. Specifically, we prove that \(a(M) \geq \frac{n}{4}\) for every planar multigraph \(M\) and that this lower bound is tight. Then, we study the case when the number of pairs of vertices with parallel edges, which we denote by \(k\), is small. In particular, we prove the lower bound \(a(M) \geq \frac{2}{5}n-\frac{k}{10}\) and that the Albertson-Berman conjecture for simple graphs, assuming that it holds, would imply the lower bound \(a(M) \geq \frac{n-k}{2}\) for multigraphs, which would be better than the general lower bound when \(k\) is small. Finally, we study the variant of the problem where the plane multigraphs are prohibited from having \(2\)-faces, which is the main non-trivial problem that we introduce in this article. For that variant without \(2\)-faces, we prove the lower bound \(a(M) \geq \frac{3}{10}n+\frac{7}{30}\) and give a construction of an infinite sequence of multigraphs with \(a(M)=\frac{3}{7}n+\frac{4}{7}\).