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

A graph \(G\) is said to be a an interval graph, if for each vertex \(u\) of \(G\), one can assign a set \(A_u\) which is a finite union of intervals on the real line such that \(u\) is adjacent to \(v\) in \(G\) if and only if \(A_u\cap A_v\neq\varnothing\). In this paper, we introduce a class of intersection graphs and show that it is equivalent to the class of interval graphs. We also investigate interval numbers of certain intersection graphs and establish several related results.

For a graph \(G=(V(G), E(G))\), a subset \(S \subset V(G)\) is a bipartite dominating set if every vertex in \(G-S\) is adjacent to a vertex in \(S\), and if the subgraph of \(G\) induced by \(S\) is bipartite. The bipartite domination number of \(G\), denoted by \(\gamma_{bip}(G)\), is the minimum cardinality of all bipartite dominating sets of \(G\). Xi and Yue [4] claimed that for every 2-connected outerplanar \(n\)-vertex graph \(G\), \(\gamma_{bip}(G) \leq \lceil \frac n 3 \rceil\), and that this bound is sharp. In this paper, correcting the result, we prove that \(\gamma_{bip}(G) \leq \lceil \frac 38 n \rceil\), where this bound is sharp.

In this article, we obtain the determining number and the metric dimension of the zero-divisor graph of the ring of integers modulo \(n\) and of non-Boolean semisimple rings. For Boolean rings, an upper bound for these parameters is established. While the determining number and metric dimension of \(\Gamma(\mathbb{Z}_n)\) are known in the literature, we provide an alternative derivation based on a structural decomposition of the graph via generalized join. This approach offers a direct and unified method to compute these parameters. Further, we determine these parameters for joins of vertex-transitive graphs and investigate certain questions concerning the relationship between determining number and metric dimension.

Motivated from the concept of strong regularity in the graph theory, few varieties of definitions for strongly regular signed graphs have been introduced. The initial one, which is due to Zaslavsky and the others are given by Stanic and Ramezani. The definition given by Stanic covers all the others. In this paper we provide some constructions for each of the definitions.

In this paper, we prove that if a graph does not contain any cycle of length greater than \(4\), then the square of its line graph is perfect. As an application, we give a concise proof of a known result: the strong chromatic index of a bipartite graph that does not contain any cycle of length greater than \(4\) is at most \(\Delta^2\), where \(\Delta\) represents the maximum degree of the graph. This latter result provides a partial affirmative answer to some known conjectures on upper bounds for the strong chromatic index of graphs.

Recently, Luo [3] introduced the Adding–Swapping Mapping Method to provide an alternative and constructive proof of Stanley’s [4] conjecture on perfect square permutations in \(S_n\) and asked whether the method extends to higher powers. In this paper we answer that question in a more limited but precise structural sense. For each fixed \(k\ge 2\), we define the \(k\)-signature \(R_k(w)\) recording the cycle-count vector modulo \(\gcd(m,k)\) in each length \(m\), and we prove a local residue transition law describing how the insertion map \(D_i\) updates the signature once the cycle length of the insertion point is specified. We also prove explicitly that every \(k\)-th power permutation has zero \(k\)-signature, so the signature gives a necessary obstruction to being a \(k\)-th power. This yields a residue-based partition of \(S_n\) that serves as an indexing scheme for insertion updates. We then show that for \(k\ge 3\) the insertion family does not preserve the class of \(k\)-th powers, explaining why the square case is exceptional from the standpoint of Luo’s method. Finally, we include explicit small-\(n\) data for \(k=3,4\) and prove that the density of \(k\)-th powers in \(S_n\) tends to \(0\) as \(n\to\infty\).

This article studies edge irregular \((k)\)-labelings of complete graphs \((K_n)\) and aims to improve the existing upper bound for the edge irregularity strength \((es(K_n))\) through an algorithmic approach. The improvement is achieved using the branch and bound algorithm design strategy, whose selection is important because of the problem structure, computational complexity, possible serial or parallel execution, and accuracy requirements. Labeling complete graphs is difficult because the number of edges grows rapidly and many triangles are involved, making it challenging to maintain unique edge weights while searching for optimal labels. Since complete graphs serve as supergraphs for many graph families, results on them are particularly valuable. In 2018, Asim et al. proposed an algorithmic solution for complete graphs and gave the upper bound \((es(K_n)\leq E\log_2 |V|)\). This article uses the branch and bound strategy to address edge deficiency and improve that bound. Computational experiments are conducted for higher-order graphs, where the algorithm recursively generates constrained combinatorial structures to ensure unique edge weights. The results show that the proposed branch and bound algorithm significantly improves the upper bound for \((es(K_n))\) compared with previous results.

In finite desarguesian projective planes of prime power order \(q\), we consider the MDS codes obtained from ovals and generate new codes for the purpose of permutation decoding. We show that those new codes are \([q^2-1,3,(q-1)^2]_q\) codes and have \(s\)-PD-sets for \(s\le q-1\).